我试图理解伪码下面的算法的时间复杂度:
让nums具有数字数组列表

sort(nums)
while(nums.size() > 1) {
   // remove two elements
   nums.remove(0);
   nums.remove(0);

   nums.add(some_number);
   sort(nums);
}

sort(nums)是指(N)Log(N)
nums.remove(0)O(N)
nums.add()O(1)
现在该算法的时间复杂度是多少?

最佳答案

最后的复杂性是O(n² log n)因为你做了n倍的操作O(n log n)
请记住,估计复杂度(O(...))与建立操作总数(通常由时间运算给出时间函数T(...))是不一样的,它们是两个不同的概念。一个很好的介绍可以是Analysis of Algorithms
因此,O(...)符号是上界,但T(...)是真正的步骤。
您可以尝试精确计算T函数,也可以通过改进O来降低上限,但它们始终是不同的函数,因为O适用于所有可能条目的最坏情况。
在您的代码中,我们不知道sort函数的T,只有它们的上界是O(n log n),然后:

T(n) ≤ O(n log n) + T(3) + O((n - 1) log (n - 1)) + T(3) + O((n - 2) log (n - 2) + ...
T(n) ≤ O(n log n) + n T(3) + n O(n log n)
                               ^^^^^^^^^

在这里,我们不能精确定义T来对n-1n-2,…这就是为什么要为所有这些人建立一个更高的O(n log n)级别。然后:
T(n) ≤ O(n log n) + n T(3) + n O(n log n)
T(n) ≤ O(n log n) + O(n) + O(n² log n)
T(n) ≤ O(n² log n)

在第二个表达式中,我们有一个固定数量的上界,在这种情况下,上界将是上界中的最高值。
(remove、remove和add是T(3)goto并且忽略比较)

09-30 13:49
查看更多