Асимптотический анализ трех взаимозависимых вложенных для циклов

Question

Фрагмент кода, который я хочу проанализировать, находится ниже:

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

Я знаю, что первый цикл - это O (n), но это примерно то, что я получил. Я думаю, что второй цикл может быть O (n ^ 2), но чем больше я думаю об этом, тем меньше смысла он имеет. Любое руководство будет высоко ценится.

Answer 1

Первый цикл выполняется n раз.Каждый раз значение i растет.Для каждого такого i второй цикл выполняется i*i раз.Это означает, что второй цикл выполняется 1*1 + 2*2 + 3*3 + ... + n*n раз.

Это сумма квадратов, и формула для этого хорошо известна .Следовательно, у нас есть второй цикл, выполняющийся (n(1 + n)(1 + 2 n))/6 раз.

Таким образом, мы знаем, что всего будет (n(1 + n)(1 + 2 n))/6 значений j, и что для каждого из них третий цикл будет выполняться 1 + 2 + ... + j = j(j+1)/2 раз,На самом деле вычислить, сколько раз третий цикл выполняется в общей сложности было бы очень сложно.К счастью, все, что вам действительно нужно, это наименьшая верхняя граница порядка функции.

Вы знаете, что для каждого из (n(1 + n)(1 + 2 n))/6 значений j третий цикл будет выполнять меньше, чем n(n+1)/2 раз.Поэтому вы можете сказать, что операция sum++ будет выполняться менее [(n(1 + n)(1 + 2 n))/6] * [n(n+1)/2] раз.После некоторой быстрой умственной математики это равняется полиному максимальной степени 5, поэтому ваша программа O(n^5).

Answer 2

int sum = 0;                  
for (int i = 0; i < n; i++)            // Let's call this N
   for (int j = 0; j < i * i; j++)     // Let's call this M
      for (int k = 0; k < j; k++)      // Let's call this K
         sum++;

N - количество шагов всей программы, M - количество шагов, которые выполняют два внутренних цикла, и, наконец, K - количество шагов, которые выполняет последний цикл.

Это просточтобы увидеть, что K = j, нужно сделать j шагов.

Then M = Sum(j=0,i^2,K) = Sum(j=0, i^2, j)

(первый параметр - итератор, второй - верхняя граница, а последний параметр - то, что мы добавляем)

На самом деле теперь это сумма из n чисел для i * i.Это означает, что мы можем применить формулу ((n + 1) * n) / 2

 M = Sum(j=0,i^2,j) = ((i^2+1)*(i^2))/2 = (i^4 + i^2)/2

 N = Sum(i=0, n, M) = 1/2 * ( Sum(i=0, n, (i^4)) + Sum(i=0, n, (i^2)) )

Это хорошо известные формулы, и после небольшой игры вы получите:

 N = (n^5)/10 + (n^4)/4 + (n^3)/3 + (n^2)/4 + n/15

Это должно быть точное число шагов, которые делает цикл, но если вас интересует нотация O, вы можете заметить, что n ^ 5 - самая сильная растущая часть, поэтому решение O (n ^ 5)

Answer 3

Если вы будете методично использовать Sigma Notation, вы получите следующий результат:

Answer 4

Попробуйте подсчитать, сколько раз выполняется внутренний цикл:

Средний цикл выполняется

0*0 times when i == 0
1*1 times when i == 1
2*2 times when i == 2
...
n*n = n^2 times when i == n.

Так что O(n^2).