计算算法时间复杂度的方法

Question

虽然对直观地确定算法的复杂性有些熟悉，但我对如何实际计算它有点迷茫。

对于以下代码，知道如何确定复杂性吗？

list = [...]
start = list[0]
end = null 
remove list[0] from list
while(list.length > 0) {
for(i = 0; i < list.length; i++) {
if(list[i] is immediately before start or immediately after end) {
link list[i] to start or end (populate end if null)
remove list[i] from list
} 
}
}

这假定一个有效的数据集(必须排序的元素的连续链接列表)。为了说明目的，也进行了简化;

因此，最好的情况是，如果列表已经排序，则为 O(n)，因为您只需要一个传递即可处理它们并弹出它们。

我无法确定的是最坏的情况，因为每次"while"迭代数据集都会变小至少 1 个元素(通常为 2 个或更多)，因为它假设数据集将始终有效。所以它显然小于 O(n^2)(我认为)。欢迎所有想法。

谢谢！

更新绘制出来后，它似乎是 O(nlogk(n))，其中 k = n ^ (2/(n+1)) 这算作O(nlog(n))吗？我不清楚。

Answer 1

Big O 表示法旨在为函数的增长率提供上限，因此您必须考虑最坏的情况。

在最坏的情况下，我会假设在每次迭代中数据集将变小 1 个元素，因此您将执行的操作数量将受n + n-1 + n-2 ... + 2 + 1的约束，等于(n+1)*n / 2即 O(n^2)