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

Question

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

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

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

Answer 1

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

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))

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

Значит, O(n log n) прав.

Answer 2

Лучший подход к этому - рассмотреть, сколько шагов предпримет алгоритм.

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

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

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

Так что это где-то между O (n) и O (n ^ 2) .... немного больше анализа того, как уменьшение шагов во внутреннем цикле должно привести вас туда. РЕДАКТИРОВАТЬ: ... Хотя, похоже, что люди уже отдали его:)

Answer 3

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