асимптотический анализ фрагмента кода

Question

Мне нужно найти большое время O бега в следующем фрагменте:

sum =0; 
for (int i=1; i<n; i++) { 
    for (int j=1; j< n/i; j++) { 
    sum = sum +j; 
    } 
} 

Я знаю, что внешний контур О (п), но у меня возникают проблемы, анализируя внутреннюю петлю. Я думаю, что это O (log n).

Answer 1

Как сказал Дэйв, это O (n log n), потому что внутренний цикл равен O (log n).

Answer 2

Давайте просто напишем это в этом псевдо-математическом стиле.

sum i <- [1..n] (sum j <- [1..n/i] 1) 

Внутренний цикл (сумма) необходимо

n/i 

итераций, что делает весь срок

sum i <- [1..n] (n/i) 

Упростить сумму в соответствии с законом распределения:

n * (sum i <- [1..n] (1/i)) 

Внутренний su m во многом аналогичен интегралу по 1/x, который является логарифмическим.

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

Answer 3

Лучшим подходом к этому является рассмотрение того, сколько шагов будет выполняться алгоритмом.

Если у вас есть n элементов, вы знаете, что внешний цикл будет работать не менее n раз. Поэтому он должен быть как минимум O (n).

Сколько раз внутренний цикл должен запускаться для каждого i? Увеличивается ли он, остается неизменным или уменьшается по мере увеличения?

Понятно, что количество шагов во внутреннем цикле будет уменьшаться по мере увеличения i, и, что более важно, оно уменьшается нелинейно. Значит, вы знаете, что это не так плохо, как O (n^2).

Таким образом, он находится где-то между O (n) и O (n^2) .... немного больше анализа того, как шаги, которые уменьшаются во внутреннем цикле, должны получить вас там. EDIT: ... Хотя похоже, что люди уже дали это :)