时间复杂度：为什么是 O(nlogn)？
time complexity : why O(nlogn)?
我有一份文件说给定代码的平均时间复杂度是 O(nlog2n)
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(nlog2n)，比worst case还高。我错过了什么吗？
编辑： 文档可能容易出错，那么在那种情况下，上述代码的平均时间复杂度是多少，为什么？
对于给定的 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 次？
我有一份文件说给定代码的平均时间复杂度是 O(nlog2n)
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(nlog2n)，比worst case还高。我错过了什么吗？
编辑： 文档可能容易出错，那么在那种情况下，上述代码的平均时间复杂度是多少，为什么？
对于给定的 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 次？