0

这是我按升序对列表进行排序的代码。我在函数中使用了函数。现在我想计算这个函数的时间复杂度。从我的角度来看，我计算出每次函数“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)
4

3 回答 3

1

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

因此，您实际上可以为您的函数正在执行的工作量编写一个快速重现：

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

因为你在很长的列表上递归两次，n/2并n^2努力重新加入它们。

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

但是，有一种方法可以编写您的unite函数，使其运行得更快、更O(n)及时。在这种情况下，您将（通过与上述类似的分析）O(nlog(n))工作。

于 2013-12-12T19:51:44.587 回答
0

对一个 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-09T03:51:27.747 回答
0

上述代码的时间复杂度（不是空间复杂度）为O(nlog(n)).

n开始时列表中有元素，我们n/2每次递归地将该列表划分为元素front，并back使其成为O(log(n))步骤。现在，对于每个步骤，我们只在函数中和函数O(log(n))中迭代每个元素一次，这使得函数变得复杂。 l1l2uniteuniteO(n)

因此，对于O(log(n))除法和O(n)联合步骤，使得该算法O(nlog(n))具有时间复杂度。

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

于 2015-08-09T20:52:24.807 回答