Что такое Big-O вложенного цикла, где количество итераций во внутреннем цикле определяется текущей итерацией внешнего цикла?

Question

Что такое временная сложность 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) еще?

Answer 1

Да, это все еще O (n ^ 2), у него меньший постоянный коэффициент, но это не влияет на нотацию O.

Answer 2

Да. Напомним определение Big-O: O (f (n)) по определению говорит, что время выполнения T (n) ≤ kf (n) для некоторая константа k . В этом случае количество шагов будет (n-1) + (n-2) + ... + 0 , что переставляет сумму от 0 до n-1; это

Т (п) = (п-1) ((п-1) + 1) / 2 .

Переставьте это, и вы увидите, что T (n) всегда будет ≤ 1/2 (n & sup2;); по определению, таким образом T (n) = O (n & sup2;) .

Answer 3

Это N в квадрате, если вы игнорируете System.out.println. Если вы предполагаете, что время, затрачиваемое на это, будет линейным по выходным данным (что, разумеется, может и не быть), я подозреваю, что в итоге вы получите O ((N ^ 2) * log N).

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

Answer 4

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

Answer 5

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

Answer 6

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