Что такое Big-O вложенного цикла, где число итераций во внутреннем цикле определяется текущей итерацией внешнего цикла?
Какова сложность времени Big-O следующих вложенных циклов:
for(int i = 0; i < N; i++) { for(int j = i + 1; j < N; j++) { System.out.println("i = " + i + " j = " + j); } } Было бы еще O (N ^ 2) ?
Да, он все еще O (n ^ 2), он имеет меньший постоянный коэффициент, но это не влияет на нотацию O.
Да. Напомним определение Big-O: O (f (n)) по определению говорит, что время выполнения T (n) ≤ kf (n) для некоторой константы k . В этом случае число шагов будет (n-1) + (n-2) + … + 0 , которое перестраивается до суммы от 0 до n-1; это
T (n) = (n-1) ((n-1) +1) / 2 .
Переупорядочите это, и вы увидите, что T (n) всегда будет ≤ 1/2 (n²); по определению, таким образом, T (n) = O (n²) .
Это квадрат N, если вы игнорируете System.out.println. Если вы предполагаете, что время, затраченное на это, будет линейным в его выходе (что, конечно, это может быть не так, конечно), я подозреваю, что вы закончили с O ((N ^ 2) * log N).
Я упоминаю, что это не придирчиво, а просто указать, что вам нужно просто не учитывать очевидные циклы при разработке сложности – вам нужно посмотреть на сложность того, что вы называете.
Да, это было бы в квадрате. Фактическое количество шагов было бы суммой от 1 до N, которая равна .5 * (N – 1) ^ 2, если я не ошибаюсь. Big O учитывает только высокий экспоненту и константы, и, таким образом, это все еще N квадратов.
Если у вас N = 10, то итерации будут следующими: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (это: десять итераций плюс девять итераций плюс восемь итераций … и т. д.).
Теперь вам нужно найти в дополнение, сколько раз вы можете получить N (10 в примере):
1: (10), 2: (9 + 1), 3: (8 + 2), 4: (7 + 3), 5: (6 + 4). Это 5 раз … и содержит 5 итераций.
Теперь вы знаете, что у вас есть пять десятков + 5:
10 (5) + 5
В терминах f (n) (или N) легко видеть, что это будет:
f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 … это точно сложность этого вложенного цикла.
Но, учитывая асимптотическое поведение Big O, мы можем избавиться от менее значимых значений f (n), которые являются единственным n и знаменателем.
Результат: O (n ^ 2)
AFAIL, начинающийся с внутреннего цикла через внешние, является адекватным способом вычисления сложности вложенных циклов. 