java - 时间复杂度 : why 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)。

average case怎么可能是O(nlog₂n)，比worst case还高。我错过了什么吗？

编辑: 该文档可能容易出错，那么在那种情况下，上述代码的平均时间复杂度是多少，为什么？

Answer 1

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

对所有 k 值取平均值得出:(n/1 + n/2 + n/3 + ... + n/n)/n。那是第 n 个 harmonic number .调和数趋向于 log(n)。

因此这段代码的平均运行时复杂度是 log(n)。那是 O(log n) 或等效的 O(log_2 n)。

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