Блог

Является ли большая сложность O n/1 n/2 n/3 … n/n O(nlogn) или O(n)? Я хочу знать это для вычисления всех делителей всех чисел от 1 до n. Мой подход состоял бы в том, чтобы просмотреть все числа и отметить их кратные. Это заняло бы вышеупомянутое время.

Вы n умножили на сумму гармонического ряда, которая имеет логарифмический рост.

Так O(nlogn)