Анализ времени выполнения зависимых вложенных для

Question

0

Вот алгоритм:

int sum = 0
for (int i = 2N; i > 0; i = i / 4) 
  for (int j = 0; j < i; j+=2) 
    sum++
  end for
end for

Я полагал, что это будет linearithmi c, но это просто линейно. Я был бы рад увидеть формализованное суммирование, а не качественное объяснение. Я пытался сделать это, но мне не удалось получить линейное время выполнения.

Answer 1

На первой внешней итерации вы увеличиваете сумму примерно в N раз, во второй - примерно N / 4 раз, затем примерно N / 16 раз, и др c. Таким образом, общее число будет около N + N / 4 + N / 16 + N / 64 + ... , что эквивалентно 4N / 3 .

Вы можете легко доказать это более формальным способом, но это будет не так просто для 101 сообщества SO. Поэтому ваша сложность просто линейна.

Answer 2

Поскольку вы запросили формализованное суммирование * только 1001 * ; обратите внимание, что количество операций вашего алгоритма может быть смоделировано по серии:
\ Sum_ {п = 0} ^ {\ infty} \ гидроразрыва {N} {4 ^ п}
Что сходится к:
\ Гидроразрыва {4N} {3}

( Это можно проверить с помощью теста геометрии c series ).

Таким образом, сложность времени вашего алгоритма равна O ( N ).

Answer 3

Разрежьте его на части:

int sum = 0

Здесь у вас есть O (1).

for (int i = 2N; i > 0; i = i / 4) 

Сколько раз это будет выполняться? Допустим, он будет работать k раз и оценит k:

2N / 4 ^ k = 1 => 2N = 4 ^ k => k = log4 (2N). Чтобы упростить, давайте просто назовем k = lg (N).

for (int j = 0; j < i; j+=2) 
    sum++
end for

В первом случае это for идет до N, затем N / 4, затем N / 16, et c.

Это дает вам следующее:

∑ (N / 4 ^ i), i = 0 ... k =

N * ∑ 1/4 ^ i, i = 0 ... k

∑ 1/4 ^ i, i = 0 ... k - ряд, который меньше 4/3 , так как он останавливается в k = lg ( n) потому что внешний l oop просто запускается lg (n) раз.

Следовательно, сложность O (X <4/3 * N), следовательно, линейная. </p>