Время работы алгоритма

Question

Привет, это вопрос экзамена. Мне нужно найти время выполнения (в Big-O) следующего фрагмента кода.

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

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

Answer 1

Нет, это не O (4).

Лучший способ увидеть это - подсчитать, сколько раз цикл выполняется (фактически, это то, что делает код).

сумма (сумма (сумма (1, к = 0..j), J = 0..i * я), я = 0..n)

= сумма (сумма (J, J = 0..i * i), i = 0..n) = sum (i * i * (i * i + 1) /2,i=0..n) , который имеет порядок суммы (i^4, i = 0..n), которая порядка n^5.

По существу, поскольку средний цикл является i * i и выполняется для каждого из внутренних циклов, его нужно считать дополнительным временем.

В C++

http://codepad.org/nKJ9IUnt

1 0 
2 0 
3 6 
4 42 
5 162 
6 462 
7 1092 
8 2268 
9 4284 
10 7524 
11 12474 
12 19734 
13 30030 
14 44226 
15 63336 
16 88536 
17 121176 
18 162792 
19 215118 

Вы можете использовать эту таблицу и вычислить конечные разности (с производными финансовыми инструментами), пока результат не является константой или 0. Вы увидите, что она занимает 5 производных иметь постоянный список. Это означает, что он имеет порядок порядка n^5.

например, если у нас был список, в котором каждая разница между двумя элементами была константой, тогда список мог быть представлен линейной функцией. Если разница в разнице была постоянной, то она была бы квадратичной и т. Д. (Это не имеет значения в терминах более низкого порядка, поскольку они переводятся производной/разностью)

Answer 2

Формально использование Sigma Notation помогло бы вывести порядок роста с резкой точностью.

Answer 3

Вы можете думать просто:

In the first loop: i = n 
second loop: j = i*i => j = n^2 
third loop: k = j => k = n^2 
So, the bigO = n * n^2 * n^2 = n^5