Что такое 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)?

Источник

8 ответов

Решение

Да, это все еще 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).

Я упоминаю это не для того, чтобы быть разборчивым, но просто для того, чтобы указать, что вам не нужно просто принимать во внимание очевидные циклы при разработке сложности - вам нужно также взглянуть на сложность того, что вы называете.

Источник

Давайте проследим, сколько раз каждый цикл выполняется на каждой итерации.

      for (int i = 0; i < N; i++) {  // outer loop
    for (int j = i + 1; j < N; j++) {  // inner loop
        System.out.println("i = " + i + " j = " + j);
    }
}

В первой итерации внешнего цикла (i = 0) внутренний цикл выполняется несколько раз.

Во второй итерации внешнего цикла (i = 1) внутренний цикл выполняется несколько раз.

В третьей итерации внешнего цикла (i = 2) внутренний цикл выполняется несколько раз.

. . .

В й итерации внешнего цикла (i = N - 3) внутренний цикл выполняется несколько раз.

В й итерации внешнего цикла (i = N - 2) внутренний цикл выполняется time.

Напоследок ( Nй) итерация внешнего цикла (i = N - 1), внутренний цикл выполняется раз.

Таким образом, общее количество выполнений этого кода равно

+ + + … + + +

знак равно 0+ 1+ 2+ … + N - 3+ N - 2+ N - 1

Подставив это в формулу суммы натуральных чисел,

знак равно (N - 1)((N - 1) + 1) / 2

знак равно (N - 1)(N) / 2

знак равно ((N^2) - N) / 2

знак равно O(N^2), предполагая System.out.printlnвыполняется за постоянное время O(1).

——————

Также взгляните на эти

  1. https://stackoverflow.com/a/71805214/17112163
  2. /questions/39522799/vremennaya-slozhnost-vlozhennogo-tsikla-for/61824023#61824023
  3. /questions/59462490/on-i-funktsiya-vremennoj-slozhnosti-dannogo-koda/59574440#59574440
  4. https://stackoverflow.com/a/72046825/17112163
  5. https://stackoverflow.com/a/72046933/17112163
Источник

Если бы у вас было 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)

Источник

Да, это будет N в квадрате. Фактическое количество шагов будет суммой от 1 до N, что составляет.5*(N - 1)^2, если я не ошибаюсь. Большое О учитывает только наивысший показатель степени, а не постоянные, и, таким образом, это все еще N в квадрате.

Источник

Для данной программы:

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        println(...);

Рассмотрим n = 3:

i будут иметь значения 0, 1 и 2.

For i = 0: println will execute 3 times
for i = 1: println will execute 2 times
for i = 2: println will execute 1 times

Таким образом println функция будет выполняться 3 + 2 + 1 раз, т.е. n(n+1)/2 раза.

Следовательно, O(n(n+1)/2) = O(n^2).

Источник

AFAIL, начиная с внутреннего цикла через внешние, является адекватным способом для вычисления сложности вложенного цикла.

Источник
Другие вопросы по тегам