временная сложность: почему 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 (nlog ₂ n), что выше, чем наихудший случай.Я что-то упустил?

Редактировать: Документ может быть подвержен ошибкам, так что в таком случае, какова средняя сложность времени для приведенного выше кода и почему?

Answer 1

Для данного значения k цикл for выполняется n / k раз.(Я игнорирую округление, что делает анализ немного более сложным, но не меняет результат).

Усреднение по всем значениям k дает: (n / 1 + n / 2 + n / 3+ ... + н / н) / н.Это n'th номер гармоники .Числа гармоник имеют тенденцию к log (n).

Таким образом, средняя сложность времени выполнения этого кода равна log (n).Это O (log n) или эквивалентно O (log_2 n).

Возможно, в вашей книге был дополнительный внешний цикл, который запускал этот код n раз?