Как найти сложность этого вложенного цикла for?
Я немного запутался в этой петле for. По заданному числу n мы должны найти, сколько раз будет выполняться инструкция.
int j = 0;
for(int p = 0; p < n*n; p++ )
{
for(int q = 0; q < p; q++ )
{
j++;
}
}
Мой ответ O(n^4). Этот ответ правильный?
Ответы 1
Вы можете написать соответствующую сигму для временной сложности T(n) = sum_{p = 1}{n^2} sum_{q=1}{p} (1) = sum_{p=1}{n^2} (p) = 1 + 2 + 3 + ... + n^2 = n^2(n^2 + 1)/2 = Theta(n^4). Итак, ваш ответ правильный для количества инструкций.
@AlbertoPoljak проверьте уравнение. Есть ли какие-либо проблемы с этим?
Это было то, что меня смутило, потому что, если бы оно было меньше или равно, я был бы уверен, что это O (n ^ 4).
@Индрити нет никакой разницы! дело в количестве инструкций. Итак, p от 0 до менее n^2 имеет n^2 число! Будьте осторожны, p и q начинаются с 0.
Тогда спасибо, очень помогло.
Да, с точки зрения нотации большого О это не имеет значения. Я тоже запутался. Все хорошо.
Вы уверены? Внутренний цикл for не выполняется фиксированно n раз, но q<p, поэтому будет 0,01,012,0123 и т. д. Я не уверен, что это n^4, но могу ошибаться