Порядок роста в цикле for

Как я могу проанализировать этот фрагмент кода, чтобы сделать вывод, что это O (N)?Порядок роста в цикле for

int sum = 0; 
for (int i = 1; i < N; i *= 2) 
    for (int j = 0; j < i; j++) 
     sum++;

источник

2014-01-25 Mark

Это звучит как проблема домашних заданий. Какой анализ вы * попробовали? – chrylis

Выберите несколько достаточно малых значений для N (например, с 4) и выпишите каждую итерацию циклов, а затем решите, является ли это O (N) – Trojan

@chrylis. Я просто попытался следовать за N в цикле, поэтому результат будет (N + 2N + 4N ...), поэтому это будет N (1 + 2 + 4 ...). Но я чувствую, что этого недостаточно, чтобы утверждать, что это O (N). – Mark

Значение i во внешнем цикле увеличивается экспоненциально, вы можете думать об этом как о возрастании двоичной цифры каждый раз. Число цифр, которое требуется для представления N, - log (N). Таким образом, внешний цикл будет выполняться журнал (N) раз Внутренний цикл будет выполняться

2^0 + 2^1 + 2^2 + ... + 2^log(N)

Формула для этого geometric series будет (обновлено от комментариев Никлас Б)

1(1 - 2^log(N))/(1 - 2) 
= 2^(log(N) + 1) - 1 
~= 2N

За весь алгоритм будет O (2N + журнал (N))

, но для большого-O нотации, компонент 2N будет подавлять журнал (N), так что в целом сложность O (N)

источник

2014-01-25 01:30:45 waTeim

Это фактически '2^(log (N) + 1) - 1', что примерно равно 2N. –

Вы правы, плохо обновляете .... – waTeim

@Gopichand: O (2N + log (N)), здесь log (N) для внешнего для цикла, а 2N - для цикла внутреннего цикла. Эти два добавляются к получить общую сложность (совокупный анализ). – tanmoy

Порядок роста в цикле for

ответ

Смежные вопросы