时间复杂度：为什么是O(nlogn)？

Question

我有一份文件，上面写着给定代码的平均时间复杂度是O(nlog₂n)

Random r = new Random();
int k = 1 + r.nextInt(n);
for (int i = 0; i < n ; i += k);

我已经计算出最好情况和最坏情况：

最好情况是k=n，时间复杂度为O(1)。

最坏情况是k=1，时间复杂度为O(n)。

平均情况怎么会是O(nlog2n)呢？这比最坏情况还高。我有什么遗漏吗？

编辑： 如果文档可能存在错误，那么以上代码的平均时间复杂度是多少，为什么？

- SaadH

---

你确定你正确复制了这个问题吗？ - Eran

是的，但是这份文档可能会存在错误。 - SaadH

看起来它可以是O(logN)，如果你得到了这样一个k值。基本上，这将取决于随机数是如何生成的。 - uneq95

@uneq95，是的，O(logn)有道理，但我想要证明/一些解释。 - SaadH

@Saad 我的回答中有证明。 - Paul Hankin

Answer 1

对于给定的k值，for循环运行n/k次。（我忽略了四舍五入，这使得分析变得更加复杂，但不会改变结果）。

对所有k值求平均值得到：(n/1 + n/2 + n/3 + ... + n/n) / n。这是第n个调和数。调和数趋向于log(n)。

因此，该代码的平均运行时间复杂度为log(n)。这是O(log n)或等价的O(log_2 n)。

也许你的书有一个额外的外部循环，将这个代码运行n次？

- Paul Hankin