我试图理解伪码下面的算法的时间复杂度:
让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-1
,n-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
并且忽略比较)