Блог

Главная - Вопросы по программированию - Нотация Big O с вложенными циклами for и одиночным циклом for

Нотация Big O с вложенными циклами for и одиночным циклом for

#big-o

#big-o

Вопрос:

     int a = 0, b = 0;    
    for (i = 0; i < N; i  ) {
        for (j = 0; j < N; j  ) {
            a = a   j;
        }
    }

    for (k = 0; k < N; k  ) {
        b = b   k;
    }

Я пытаюсь определить временную сложность вышесказанного.

Я думал, что это O(n^2 n) мои рассуждения:

 n^2 : nested for loops
n   : Adding the single loop

Тем не менее, подтвержденный ответ O(n^2)

Мои вопросы: почему включен последний цикл for, поскольку это само по себе было бы O(n)

Большое спасибо за любые предложения,

Ответ №1:

В нотации Big-O вы берете компонент высшего порядка и отбрасываете другие коэффициенты умножения. Причина в том, что по мере увеличения «n» в экспоненциальном процессе добавление еще одного «n» на самом деле не сильно его меняет.

Если n=1000000 тогда n^2 есть 1000000000000 . Указание n сделать это 10000001000000 не оказывает существенного влияния. По мере n увеличения влияние становится еще более незначительным.

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

Ответ №2:

Вам не нужно упоминать O (n), потому что это арахис по сравнению с классификацией O (n ^ 2). Это та же идея, что и когда в вашем алгоритме есть часть O (n) и часть O (1) — вы не называете это O (n 1), вы называете это O (n) .

В этой статье есть хорошее объяснение: https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

Ответ №3:

Вы технически правы в том, что время выполнения равно O (n ^ 2 n), потому что начальный цикл является квадратичным, а второй — линейным. Однако соглашение с нотацией big-O заключается в том, чтобы исключить постоянные множители и члены более низкого порядка из выражения big-O, поскольку нотация big-O говорит о долгосрочном ограничивающем поведении. В результате данный ответ O(n ^ 2) является лучшим способом учета времени выполнения. Ваш ответ технически верен, но он не считается хорошим математическим стилем.

Ответ №4:

Первый набор вложенных циклов равен O (N ^ 2), а второй цикл равен O (N). Это O(max(N ^ 2,N)), которое равно O(N ^ 2) .

Как цитируется из: http://pages.cs.wisc.edu /~vernon/cs367/notes/3.COMPLEXITY.html >> ИСПЫТАЙТЕ СЕБЯ #3