algorithm - 显示运行时间的难度是 bigOmega(g(n))

Question

我在使用以下算法时遇到了一些问题:

for (int i = 1; i < n; i = 2i)
    for (int j = i; j < n; j++)
        // do something (const time)

所以证明运行时间是 O(nlogn) 并不难——但我不确定如何证明它是 Big Omega(nlogn)!凭直觉，我认为情况一定如此，因为对于给定的 n，时间复杂度在最好/最坏情况之间没有变化。

如有任何建议，我们将不胜感激!

Answer 1

在此算法中，没有最佳或最差执行路径:给定 n 的值，执行路径是固定的。所以最好和最坏的情况是一样的。

一个好的经验法则是，如果算法的控制流不是数据驱动的，那么最好和最坏的情况是相同的。

我所说的数据驱动的一个例子是快速排序算法的实现，其中始终选择主元作为数组的第一个元素。有时第一个元素会完美地拆分其余数据(最好的情况)，有时它会是最大值或最小值(最坏的情况)。