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

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

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

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


analysis big-o
person Community    schedule 10.10.2009    source источник

Ответы (3)


arrow_upward
7
arrow_downward

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

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) прав.

person Dario    schedule 10.10.2009

arrow_upward
4
arrow_downward

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

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

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

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

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

person womp    schedule 10.10.2009
comment
На самом деле это может быть O(n^2) (или, точнее, Theta(n^2)), даже если количество шагов во внутреннем цикле уменьшается. Например, подумайте о случае, когда внутренний цикл состоит из n-i шагов (что имеет место, среди прочего, в алгоритме сортировки вставками). - person JaakkoK; 10.10.2009
comment
А как насчет for i in 1..n for j in 1..i ...? Согласно вашему объяснению, это не as bad as O(n²), потому что диапазон внутренних циклов уменьшается по мере увеличения i, но на самом деле O(n²) - person Dario; 10.10.2009
comment
@jk: Забавно, всего 17 секунд разницы^^ - person Dario; 10.10.2009
comment
@Дарио: разве ты не противоречил своему ответу в этом комментарии? - person Dave; 10.10.2009
comment
@dario и @jk - вы, ребята, правы, я должен был сказать, что линейно уменьшается. - person womp; 10.10.2009
comment
@Dave: Нет, мой комментарий описывает совершенно другой цикл for, а не тот, о котором просили. - person Dario; 10.10.2009
comment
@ Дэйв - нет, он указывает, что мое объяснение слишком упрощено. У вас может быть меньший внутренний цикл, который линейно уменьшается с внешним циклом, и он по-прежнему считается O (n ^ 2). Количество шагов должно быть функционально связано на порядок. - person womp; 10.10.2009
comment
Хорошо, возвращаясь назад, я понимаю несоответствие. Тем не менее, я думаю, вы поняли суть с первого раза. - person Dave; 10.10.2009

arrow_upward
1
arrow_downward

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

person Paul McMillan    schedule 10.10.2009
comment
Вау, это было быстро; вопрос, на который я ответил, пропал :) - person Dave; 10.10.2009