Подтвердить что ты не робот

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 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;).

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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