我有一个文档说明给定代码的平均时间复杂度为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)的时间复杂性。
平均情况如何是O（nlog2n），高于最坏情况。我错过了什么吗？
编辑：文档可能容易出错，所以在这种情况下，上述代码的平均时间复杂度是什么，为什么？
对于给定的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次？