Анализ Запуск раз

Question

мне нужно дать бегущих раз для следующих за петли (в биг-Oh обозначении):

1. sum = 0 for i = 1 to n do for j = 1 to i do sum++

2. sum = 0 for i = 1 to n do for j = 1 to i^3 do for k = 1 to j do sum++

3. sum = 0 for i = 1 to n do for j = 1 to i^2 do if (j (mod i) = 0) then for k = 1 to j do sum++

Любая помощь была бы великолепной я оценил, особенно если вы могли бы объяснить, как вы дошли до ответа, чтобы я мог это понять.

Заранее благодарен!

EDIT: Оглядываясь назад, я должен, вероятно, упомянуть, что это те немногие, что я не мог понять с помощью своего учебника и заметок, остальное, что я смог решить.

Answer 1

Так что я только начал класс с очень похожим материалом, чтобы у меня не было этого места. Общая идея, что я имею в том, что время выполнения в основном основано на количестве циклов в данной программе.

Так, например, позволяет принимать ваши проблемы # 1

sum = 0 
for i = 1 to n do 
    for j = 1 to i do 
     sum++ 

С его 2 вложенных для петель времени выполнения растет экспоненциально, и поскольку вы падаете условия меньшего порядка (сумму ++ будет добавить время, но она незначительна) тем самым оставляя вам время пробега N^2.

Чтобы пойти дальше принять эту программу

sum = 0 
for i = 1 to n do 
    for j = 1 to i do 
     sum++ 
sum2 = 0 
for i = 1 to n do 
    for j = 1 to i do 
     sum2++ 

Поскольку 2 для петли спина к спине времени работы должны быть 2N^2

Надежда это было полезно = D