复杂性，产生排列

我听不太懂，你怎么去判断这个算法的时间复杂度（用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

这个过程需要输入一个序列并作为结果返回包含起始序列的所有可能排列集合的序列序列。

例：置换（[A，B，C）= [[A，B，C]，[A，C，B]，[B，A，C]，[B，C， a]，[c，a，b]，[c，b，a]]

现在，为了确定复杂性，我必须编写并求解复发方程。列表长度为0或1时，不执行任何操作。否则，运行的Ñ迭代一个循环，其中每次迭代中被调用的函数的列表上被一个元素比（N-1）短，并且然后运行的内长n-1个。

教授接着写道：

T（0）= T（1）= 1（？1，为什么它的回报或成本等）

T（N） = N *（T（N-1）+（N-1））为N> 1

然后他说，选择较低的边界，然后写入（以下简称我不明白什么）：

T（n）的> N * T（N-1）

从其中：

T（n）的>ÑT（N-1）>ñ（N-1）T（n-2）> n（n-1）*（n-2）* T（n-3）> ...> n！

即：

T（N）=Ω（！n）的

我不明白，因为它消除了（N-1）因为它已经把主要而不是等号。所以我什么都不懂。有人向我解释它会知道吗？谢谢

来源

2015-04-07 user3808470

这只是一个容易出错但非常基本的代数。

M（1）和M（0）为1的原因是因为如果你有一个带有1或0个元素的列表，那么这个列表本身就是它唯一的排列。例如{1}只有一个排列，{}也只有一个排列。所以1与本身完成的工作无关，但实际上只有一个排列组合。但是，确实，你只是简单地回报它，所以你可以这样想。

现在为更有趣/无聊的部分。

如果接受

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）+（n-1-1）））+（n-1）

T（n）= n *（（n-2）T（n-1）（k *（T（n-2）+（n-2）））+（n-1）

T（n）= n^3 + n^2 * T - 2n^2-n * T（n-2）+ n：这只是代数扩展。

如果用T（K）取代T（N-2），然后T（N-3），你会看到阶乘百通的出现，即N！ = n *（n-1）！

来源

2015-04-07 18:14:42

你的教授应该写T（0）= T（1）= Theta（1）这意味着这些情况需要一个固定的时间，但只是把一个像1这样的固定常量不改变渐近线。至于其他的，如果你相信

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

（再次我已经把大西塔强调的是，当你算操作有可能会被隐藏常数乘法器），那么你肯定拿到

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

，因为你已经减去了正项Theta（n-1）。其余的由定义阶乘。

来源

2015-04-07 18:04:44 user2566092

复杂性，产生排列

回答

相关问题