Время выполнения цикла - часть № 2 - PullRequest
Новая
       4

Время выполнения цикла - часть № 2

1 голос
/ 10 октября 2011

Это будет часть № 2 моего вопроса об анализе времени выполнения цикла

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOhSolutions.htm#PR4 содержит решения, и у меня есть вопрос о двух конкретных циклах for для

Может ли кто-нибудь объяснить мне, как выяснить время выполнения для них обоих.Спасибо!

1. 

sum = 0;
for( i = 0; i < n; i++)
    for( j = 0; j < i*i; j++)
        for( k = 0; k < j; k++)
            sum++;

2. 

sum = 0;
for( i = 0; i < n; i++)
    for( j = 0; j < i*i; j++)
        if (j % i ==0)
           for( k = 0; k < j; k++)
               sum++;

Ответы [ 2 ]

2 голосов
/ 10 октября 2011

Первый фрагмент - O(n^5). 

Top Loop    = 0 - O(n)   = O(n)   iterations
Middle Loop = 0 - O(n^2) = O(n^2) iterations
Inner Loop  = 0 - O(n^2) = O(n^2) iterations

Total = O(n^5)

Вот решение первого фрагмента в замкнутой форме: (вычислено с помощью Mathematica) 

sum = -(1/10)*n + (1/4)*n^2 - (1/4)*n^4 + (1/10)*n^5

Это полином 5-го порядка, поэтому он: O(n^5)

Второй фрагмент выглядит как O(n^4). 

Top Loop    = 0 - O(n)   = O(n) iterations
Middle Loop = 0 - O(n^2) = O(n^2) iterations
If statement enters: O(1 / n) times
Inner Loop  = 0 - O(n^2) = O(n^2) iterations

Total = O(n^4)

Вот решение второго фрагмента в замкнутой форме: (вычислено с помощью Mathematica) 

sum = -(1/12)*n + (3/8)*n^2 - (5/12)*n^3 + (1/8)*n^4

Это полином 4-го порядка, поэтому он: O(n^4)

Дальнейшее объяснение влияния оператора if:

Средний цикл повторяется от 0 до i*i. Оператор if проверяет, делится ли j на i. Но это возможно только тогда, когда j кратно i.

Сколько раз j кратно i, если 0 <= j < i*i? Точно i раз. Следовательно, только 1/i итераций среднего цикла попадет в самый внутренний цикл.

1 голос
/ 10 октября 2011

Отношение 'n', а также других переменных во второй инструкции цикла for (..., x <= n, ...) действительно определяет, насколько быстро это будет. Попробуйте визуализировать цикл for как беговую дорожку, и второе утверждение говорит о том, сколько кругов вы бы сделали. Так, например, переменная 'n' = 1000, тогда вы должны были бы пробежать один и тот же круг 1000 раз, действительно потеряв время. Надеюсь, что вы получили лучший взгляд на вещи. </p>

...