置换的阶乘时间复杂度

问题描述

我只想检查以下代码是否具有阶乘时间复杂度。即O(n！)如果n是my_str中的字符数。据我所知是这样的，但我可能遗漏了一些东西。

def perms(a_str):
    stack = list(a_str)
    results = [stack.pop()]
    while stack:
        current = stack.pop()
        new_results = []
        for partial in results:
            for i in range(len(partial) + 1):
                new_results.append(partial[:i] + current + partial[i:])
        results = new_results
    return results


my_str = "ABCDEFGHIJ"
print(perms(my_str))

---

解决方案

复杂度实际上是O((n+1)！)，虽然相当于O(n！)是一个明显比它更复杂的类。

将算法放入其运行时分析可接受的术语中，迭代地生成输入字符串的每个后缀的所有排列，直到While循环的最后一次迭代完成为止，其中它将构建整个输入字符串的排列。

在循环之前，您将生成最后一个长度为1的后缀的所有排列(仅包含最后一个字符的所有1！=1个排列的列表)。为简单起见，请将此视为循环的第一次迭代

然后，在循环的k-th迭代期间，通过将索引n-k处的字符放在已经构建的每个部分排列的所有可能位置，您可以有效地使用后缀a_str[n-k+1:]以前的所有排列来构建增量更大后缀的排列。每次迭代所做的总功与该迭代期间生成的所有新部分置换字符串的总长度成正比，即每个部分置换的长度k乘以部分置换的数量k!：k*k!。

考虑到k的范围从1(生成最后一个字符的初始单个排列时)到n(在上一次迭代期间负责生成最终出现在输出中的所有n!排列)，整个算法过程中所做的全部工作可以由简单的和给出：

当您求解这个总和(表示在算法过程中构建的所有部分排列的总长度)时，您会得到：

置换生成算法的最佳运行时间为O(n*n!)，因为这是您需要生成的输出数组的总长度。但是，O((n+1)!) = O(n*n!)因为：

O((n+1)!) = O((n+1)n!) = O(n*n! + n!) = O(n*n!)

这意味着上面的算法仍然是渐近最优的，即使它在构建部分排列方面确实做了一些不必要的工作，这些部分排列本身并不直接构成最终输出(这样，基于交换元素而不是迭代地构建部分排列的排列生成算法可以稍微快一点)。

您可以使用此仪表化版本的算法和一些测试用例检查我的数学：

def perms(a_str):
    total_cost = 0 # total cost of creating all partial permutation strings
    stack = list(a_str)
    results = [stack.pop()]
    total_cost += len(results[0]) # increment total cost
    while stack:
        current = stack.pop()
        new_results = []
        for partial in results:
            for i in range(len(partial) + 1):
                next = partial[:i] + current + partial[i:]
                total_cost += len(next) # increment total cost
                new_results.append(next)
        results = new_results
    return results, total_cost

from math import factorial

def test(string):
    n = len(string)
    print(f'perms({string}):')
    ps, total_cost = perms(string)
    # print(ps)
    print("optimal cost:", n * factorial(n))
    print("total cost:", total_cost)
    print("expected cost (sum):", sum([k * factorial(k) for k in range(1, n+1)]))
    print("expected cost (closed form):", factorial(n + 1) - 1)
    print()

tests = [''.join([chr(i) for i in range(ord('A'), ord('A')+j)]) for j in range(1, ord('I') - ord('A'))]
for t in tests: test(t)