Проблема с вложенным циклом времени выполнения - PullRequest
Новая
       22

Проблема с вложенным циклом времени выполнения

2 голосов
/ 11 сентября 2011

Я обдумывал эту проблему уже несколько дней и одержим подсчетом, сколько раз будет выполняться второй вложенный цикл for.Я полагаю, что у меня есть правильная формула для определения времени выполнения для двух других циклов for, но этот третий заставил меня повесить трубку.У меня первый цикл работает n-1 раз.Уравнение для определения количества выполнений цикла # 2:Суммирование от 1 до n-1.Если бы кто-нибудь мог помочь мне понять, как узнать количество выполнений цикла # 3, это было бы очень полезно. 

    for ( int i=1; i<=n-1; i++ ) {
        for ( int j=i+1; j<=n; j++ ) {
            for ( int k=1; k<=j; k++ ) {
            }
        }
    }

1 Ответ

2 голосов
/ 11 сентября 2011

Третий цикл выполняется C раз: 

C = Sum( Sum ( Sum ( 1 , k = 1 .. j ) , j = i+1 .. n ) , i = 1 .. n-1 )
  = Sum( Sum (           j            , j = i+1 .. n ) , i = 1 .. n-1 )
  = 2 + 3 + 4 + ... + n
      + 3 + 4 + ... + n
    ...
                    + n
  = 2*1 + 3*2 + 4*3 + 5*4 + ... + n*(n-1)
  = (1*1 + 1) + (2*2 + 2) + (3*3 + 3) + ... + ((n-1)*(n-1) + n-1)
  = (1^2 + 2^2 + ... (n-1)^2) + (1 + 2 + 3 + ... + (n-1))
  = (n-1)*n*(2*n-1)/6 + (n-1)*n/2 
  = (n-1)*n*(2*n+2)/6
  = O(n^3)

Здесь я использовал формулы: 

1^2 + 2^2 + ... + m^2 = m*(m+1)*(2*m+1)/6

и 

1 + 2 + ... + m = m*(m+1)/2
...