算法的时间复杂度

这里是我按升序对列表进行排序的代码。我已经在函数中使用了函数。现在我想计算这个函数的时间复杂度。从我的角度来看，我已经计算过，当函数“sort”完成循环时，每次调用函数“unite”。所以这个函数每次都使用两个函数。所以我得出结论：这个函数的复杂性是O（nlog（n））。我是本章新手。所以我想知道如何计算这种复杂性。上面的答案只是我的近似值。我也不知道真正的答案，也没有任何解决方案或提示。所以请在你给予时描述你的答案。谢谢。这是我的代码。算法的时间复杂度

def sort(lst): 
    def unite(l1, l2): 
     if len(l1) == 0: 
      return l2 
     elif len(l2) == 0: 
      return l1 
     elif l1[0] < l2[0]: 
      return [l1[0]] + unite(l1[1:], l2) 
     else: 
      return [l2[0]] + unite(l1, l2[1:]) 

    if len(lst) == 0 or len(lst) == 1: 
     return lst 
    else: 
     front = sort(lst[:len(lst)/2]) 
     back = sort(lst[len(lst)/2:]) 

     L = lst[:] # the next 3 questions below refer to this line 
     return unite(front, back)

来源

2013-12-12 user3096874

从哪儿来'sort4'？ – Hyperboreus

实际上，它至少是O（n^2），因为'unite'为大小为n1 + n2 = n的输入创建O（n^2）个副本。（并且O（n log n）在任何意义上都不是近似值。） – delnan

但是我已经看到了几个函数中调用函数的例子。它们具有O（log（n））的复杂度。 – user3096874

第一步是要注意的是，真正的工作是在unite步你的代码，这确实n^2工作，因为你正在创建新的列表，每次被完成。

所以，实际上你可以编写一个简单的复发的工作量你的函数是做：

W(n) = 2W(n/2) + n^2

，因为你对那些长度n/2名单递归两次，做n^2工作重新加入他们。

现在，考虑递归树 - 在树的某个级别（称为级别i），您正在做2^i * (n/2^i)^2工作。这是关于O(n^2)每个级别的工作，并且有log(n)级别，所以你在做O(n^2log(n))工作。

但是，有一种方法可以编写您的unite函数，以便运行速度更快，时间更短。在那种情况下，你会（通过类似的分析）O(nlog(n))工作。

来源

2013-12-12 19:51:44 AVP

第n^2号不是正确的答案。我仍然没有任何答案。 – user3096874

排序在n元素向量上执行的时间是T（n）。

T(n) = 2 T(n/2) + n 

    = 2 [2 T(n/4) + n/2] + n 

    = 4 T(n/4) + 2n 

    = 4 [2 T(n/8) + n/4] + 2n 

    = 8 T(n/8) + 3n 
    ........ 

    = 2k T(n/2k) + k n 

    = 2log2 n T(1) + (log2n) n because T(1)=O(1) 

    = n + n log2 n  

    = O(n log n)

有一种简单的方法来记住排序解递归函数的复杂性。 T（选择排序）= O（n^2）和T（合并排序）= O（nlogn）。显然，你的代码是合并排序类型。

来源

2015-03-09 03:51:27

上述代码的时间复杂度（非空间复杂度）为O(nlog(n))。

有在列表中开始n元素，我们递归划分在每次n/2元素列表分为front和back这使得它O(log(n))步骤。现在，对于O(log(n))步骤中的每一个，我们遍历l1和l2中的每个元素，仅在unite函数中作用一次，这使得复杂度为unite函数O(n)。

因此，对于O(log(n))部门和O(n)联合步骤使得该算法的时间复杂度为O(nlog(n))。

其他答案正在讨论unite函数的空间复杂度为O(n^2)，但问题标题明确询问时间复杂度而不是空间复杂度。

来源

2015-08-09 20:52:24

算法的时间复杂度

回答

相关问题