Сколько раз выполняется этот оператор в трижды вложенном цикле?

Question

Это моя проблема

for(i=1;i<=n;i++) 
    for(j=1;j<=i;j++) 
     for(k=1;k<=j;k++) 
      x++; 

Теперь я хочу знать заявление х ++; сколько итераций ??? Я хочу знать формулу решения.

Answer 1

Вы ищете значение следующего суммирования:

Sum(i from 1 to n) 
     Sum (j from 1 to i) 
      Sum (k from 1 to j) 
       1 

Работа изнутри:

Sum(i from 1 to n) 
     Sum (j from 1 to i) 
      Sum (k from 1 to j) 
       1 
= Sum(i from 1 to n) 
     Sum (j from 1 to i) 
      j 

= Sum(i from 1 to n) 
     i(i + 1)/2 

Отсюда, мы получаем

сумму (я от 1 до n) i (i + 1)/2

= (1/2) Сумма (я от 1 до п) (я + I)

= (1/2) (сумма (я от 1 до п) я + сумма (я от 1 до п) я)

= (1/2) (п (п + 1) (2n + 1)/6 + п (п + 1)/2)

Вы можете попытаться упростить этот многочлен, чтобы получить чистое, точное значение. Если вам просто нужна асимптотическая верхняя граница, это Θ (n).

Согласно Wolfram Alpha, это

п /6 + п /2 + п/3

Надеется, что это помогает!