下面代码片段的最佳和最差情况是什么?

Question

for (int index = 1; index < n; index *= 2) {
int counter = 0;
while (counter < n) {
counter++;
}
}

以n为函数的Big-Theta表示法确定其最佳和最差运行时间。

我认为最坏的情况是n*log(n)，但我不确定最好的情况是什么。

Answer 1

时间复杂度确实是0(𝑛log𝑛)，但没有最佳或最差的概念。

这种最好或最差的概念只有在给定的𝑛可能存在一些变化时才起作用。例如，排序算法将其时间复杂度表示为输入的大小，但是输入的排序方式仍然存在一些变化(它已经排序了吗?它是反向排序的吗?

等)。在这个问题中，只有𝑛作为输入，没有其他，所以时间复杂度就是这样——没有最好，也没有最差。