Найти временную сложность данного вложенного цикла

Какова временная сложность для этого цикла ниже?

int sum = 0;
for(int n = N; n > 0; n/=2)
    for(int i = 0; i < n; i++)
    sum++

Я выяснил, что внутренний цикл выполняется N + N/2 + N/4 + N/8 + ... + 1 раза, но теперь я не знаю, что делать дальше. Как мне получить тильду или большую букву «О» из этого цикла?

Заранее спасибо.


algorithm time-complexity big-o tilde
person belismau    schedule 07.09.2020    source источник
comment
Подсказка: N + N/2 + N/4 + ... + 1 = 2*N   -  person tobias_k    schedule 07.09.2020
comment
Почему оно равно 2*N?   -  person belismau    schedule 07.09.2020
comment
Если ответ 2*N, то тильда — это 2N, а большая буква O — это N, но мне интересно, как вы получили 2*N   -  person belismau    schedule 07.09.2020
comment
@belismau: попробуйте, скажем, N = 16, и вы поймете.   -  person Yves Daoust    schedule 07.09.2020
comment
Я не собираюсь вам это доказывать, но интуиция довольно проста. Вы начинаете с N, и разница с 2N равна N. Вы добавляете N/2, и разница уменьшается до N/2, вы добавляете N/4, она уменьшается до N/4 и так далее. По мере того, как вы добавляете новые термины, разница с 2N соответственно уменьшается, становится все меньше и меньше, но никогда не достигает 2N.   -  person tobias_k    schedule 07.09.2020
comment
Ага, значит, если N = 16, получится 16+8+4+2+1=31, что почти равно 2N?   -  person belismau    schedule 07.09.2020
comment
@belismau это не 2N. это серия ГП   -  person Maya    schedule 07.09.2020
comment
что такое ГП? @Ава   -  person belismau    schedule 07.09.2020
comment
Геометрическая прогрессия   -  person Maya    schedule 07.09.2020
comment
Возможно, мне следовало выразиться яснее: сумма 1, 2,... 2^n равна 2^(n+1)-1, а не 2^(n+1), и аналогично сумма вашего ряда не равна 2N а 2Н-1, но для анализа это не имеет значения.   -  person tobias_k    schedule 07.09.2020
comment
@tobias_k это (2^n - 1)   -  person Maya    schedule 07.09.2020
comment
@Ava Уверен, что 1+2+4+... +2^n немного больше, чем 2^n-1   -  person tobias_k    schedule 07.09.2020
comment
И, конечно, это только в том случае, если N в цикле OP является степенью двойки; в противном случае может получиться значительно меньше 2N или 2N-1 из-за деления нечетных чисел на пол, но никогда больше.   -  person tobias_k    schedule 07.09.2020
comment
@belismau временная сложность O (2 ^ n)? Вы поняли или все еще хотите, чтобы я объяснил?   -  person Maya    schedule 07.09.2020
comment
Я не понимаю. Пожалуйста, объясните еще раз. Разве это не O(2N)?   -  person belismau    schedule 07.09.2020
comment
@belismau Да, это O(2N) = O(N) (в теории сложности постоянные множители опущены)   -  person MBo    schedule 07.09.2020

Ответы (2)


arrow_upward
0
arrow_downward

Big-O из этого цикла равен O(N), так как зависимость количества итераций от N является линейной.

Около 1/2 + 1/4 + 1/8 + ... https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF< /а>

О Big-O https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

person Pavel Matrenin    schedule 07.09.2020
comment
Это сумма бесконечных рядов GP. - person Maya; 07.09.2020

arrow_upward
0
arrow_downward

N + N/2 + N/4 + N/8 + ... + 1 образует GP (геометрический прогресс), который в сумме дает 2N. Определяя временную сложность в терминах большого O, мы отбрасываем константу. Таким образом, временная сложность вашей проблемы составляет O (N).

person another_CS_guy    schedule 07.09.2020
comment
Как преобразовать N + N/2 + N/4 + N/8 + ... + 1 в 2N? - person belismau; 08.09.2020
comment
В первый раз значение 'n' внешнего цикла равно N, поэтому внутренний цикл будет выполняться N раз, в следующий раз он будет делиться на половину bcoz от n/=2, поэтому внутренний цикл будет выполняться N/2 раза, в следующий раз внутренний цикл будет выполняться N/4 раз и так далее... - person another_CS_guy; 09.09.2020