Мне пришлось определить большую сложность этого фрагмента кода. Я думал, что ответ nlogn, но, по-видимому, его n. Может ли кто-нибудь объяснить, почему это так?Какова сложность этого фрагмента кода
void funct(int n)
{
for (int i = n; i > 0; i /= 2)
for(int j = 0; j < i; j++)
printf("%d\n", j%2);
}
Это геометрическая прогрессия В первый раз, когда выполняется внутренний цикл n раз. Второй раз исполняется n/2 раз. и т.д. ... Итак, мы имеем следующую последовательность: п + п/2 + п/4 + ... 1 поэтому окончательная формула:
n*(1 - (1/2)^(log n))/(1/2)
что эквивалентно п
Внешний цикл, так как я уверен, что вы можете увидеть, выполняется log(n) раз. Внутренний цикл выполняется в среднем log(n)/2 раз. Таким образом, оператор printf выполнен log(n) * (log(n)/2) раз, который равен n/2. Таким образом, сложность кода O (n).
'i/= 2' Внешний цикл - это exectern' log (n) 'times – kostek
@kostek О, я этого не понимал. Благодарю. Обновление сейчас. – Daniel
Я согласен с результатом O (n), но внутренний цикл * не * выполняется 'log (n)/2' раз. Если кто-то использует аргумент «в среднем» в вопросах O-нотации, аргумент в большинстве случаев неверен. Итерации для внутреннего цикла должны быть проанализированы как функция итерации внешнего цикла, и необходимо проверить весь * термин. Вам повезло, что результат правильный. – mastov
Посмотрите, что эти проблемы могут быть решены с использованием Double Sigma's: Let $ представляет sigma. так эта проблема:
$(i=n downto 0 by a factor of 2)$(j=0 to i-1) 1
, где 1 представляет блок стоил
теперь для внутренней сигмы его сумма 1i раз, что является = я
Теперь проблема заключается в $(i=n downto 1 by a factor of 2) i
, который представляет собой сумму i значений, т.е. n+n/2+n/4+...+1(when n/2^x=1 or after log(n) terms)+0
или n*(1+1/2+.....log(n) terms)
которая является сходящимся Geometric progression. и результат будет n*(1 - (1/2)^(log n))/(1/2) i.e O(n)
Это немного сложнее, если учесть, что 'n' не является степенью 2, но результат будет таким же. Тем не менее, наконец, кто-то с правильным подходом и без размахивания руками :-) – mastov