Вы можете решить этот шаг за шагом от внутреннего к внешнему l oop:
func(n)
x = 0
for i = 1 to n do
for j = 1 to i do
for k = j to i + j do
x <- x + 1
return x
Начните с самого внутреннего утверждения. x <- x + 1 - это отдельная инструкция, поэтому
func(n)
x = 0
for i = 1 to n do
for j = 1 to i do
for k = j to i + j do
Theta(1)
return x
Следующее l oop выполняется (i + j) - j + 1 = i + 1 раз:
func(n)
x = 0
for i = 1 to n do
for j = 1 to i do
Theta(i)
return x
Продолжая таким образом, мы получаем:
func(n)
x = 0
for i = 1 to n do
Theta(i^2)
return x
и, наконец, используя тот факт, что сумма квадратов от 1 до n равна n(n + 1)(2n + 1)/6 = n^3/3 + n^2/2 + n/6 = Theta(n^3):
func(n)
x = 0
Theta(n^3)
return x
Поскольку все остальные операторы выполняются в постоянном времени, общая сложность Theta(n^3).