生成排列的算法的复杂性

Question

我无法理解您如何确定该算法的时间复杂度（用 Python 编写，但适用于任何语言）：

def permutazioni(list):
    n = len(list)
    if n == 1 or n == 0: 
        return [list]
    else:
        risult = []
        for i in range(n):
            primo = list[i]
            listaDegliAltri = list[:i] + list[i + 1:]  
            perms = permutazioni(listaDegliAltri)
            for perm in perms:
                risult.append([primo] + perm)
    return risult

此过程将一个序列作为输入，并将 return 的结果作为包含起始序列所有可能排列集合的序列序列。

示例：排列([a, b, c]) = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a , b], [c, b, a]]

现在，为了确定复杂度，我必须编写并求解递归方程。当列表为 long 0 或 1 时，不执行任何操作。否则，您运行一个 n 迭代的循环，其中每次迭代都会在一个元素短于 (n-1) 然后你运行一个内部的 long n-1.

教授接着写道：

T(0) = T(1) = 1（1为什么？是return的成本还是其他？）

T(n) = n*(T(n-1) + (n-1)) 对于 n>1

然后他说选择下边界然后写（后面我什么都不懂）：

T(n) > n*T(n-1)

来自：

T(n) > nT(n-1) > n(n-1)T(n-2) > n(n-1)*(n-2)*T(n-3)> ... > n!

即：

T(n) = Ω(n!)

我不明白，因为它删除了 (n-1) 并且因为它用大号代替了等号。所以我什么都不懂。有人向我解释一下会知道吗？谢谢

Answer 1

你的教授可能应该写成 T(0) = T(1) = Theta(1)，意思是这些情况需要常数时间，但仅仅输入一个固定常数，比如 1 通常不会改变渐近线.至于其他的，如果你相信

T(n) = n*(T(n-1) + Theta(n-1))

（我又放了 big-Theta 来强调当你计算运算时可能有隐藏的常量乘数），那么你显然明白了

T(n) > n*T(n-1)

因为你减去了正项 Theta(n-1)。其余遵循阶乘的定义。

Answer 2

这只是大量容易出错但非常基础的代数。

M(1) 和 M(0) 为 1 的原因是，如果您有一个包含 1 个或零个元素的列表，那么该列表本身就是它的唯一排列。例如{1}只有一种排列，{}也是如此。所以 1 与完成的工作本身无关，但实际上只有一种排列。但是，您只是 return 也是事实，因此您可以这样想。

现在更 interesting/boring 部分。

如果你接受

T(0) = T(1) = 1

T(n) = n*(T(n-1) + (n-1)) 对于 n>1

接下来就是乏味的代数了。所以先说 T(n-1)=T(k)。所以

T(n) = n*((k*(T(k-1) + (k-1))) + (n-1))

T(n) = n*(((n-1)*(T(n-1-1) + (n-1-1))) + (n-1) )

T(n) = n*((k*(T(n-2) + (n-2))) + (n-1))

T(n) = n^3 + n^2*T(n-2) - 2n^2-n*T(n-2)+n：这只是代数展开。

如果用 T(k) 替换 T(n-2)，然后替换 T(n-3)，您将看到阶乘模式出现，即 n! = n*(n-1)!

生成排列的算法的复杂性

Complexity of the algorithm that generates permutations

algorithm

permutation

time-complexity