Все, что вам нужно знать о нотации Big-O

Если вы изучаете информатику или курсы, связанные с алгоритмами, вы наверняка сталкивались с термином “нотация Big O”. Это распространенный способ описания эффективности и сложности вашего кода. Несмотря на то, что в некоторых учебных программах он не является обязательным, изучение нотации Big O может быть полезным при анализе вашего алгоритма. На собеседованиях в колледже она иногда может стать тем преимуществом, которое необходимо, чтобы пройти отбор.

Что такое Big-O?

Нотация Big O описывает сложность вашего кода с помощью алгебраических терминов. На самом деле эта нотация представляет собой функцию, как в математических, так и в вычислительных терминах: O( ). Буква O используется, поскольку она представляет собой “порядок функции”.

Математически O( ) описывает скорость роста функции (f(x)) при увеличении x от 0 до положительной бесконечности. Проще говоря, это оценка того, как изменится значение при увеличении x в функции. В конечном счете, мы хотим знать, как быстро функция может расти при большом x. Как правило, член с наибольшей мощностью x сохраняется, а члены с меньшей мощностью опускаются. Например, если f(x) =9x 2-5x+10, то f(x) = O(x 2 ). Это говорит о том, что функция будет квадратично возрастать по мере приближения x к положительной бесконечности.

В информатике использование нотации big O больше связано с вычислительной сложностью. Здесь big O используется для нахождения асимптотической верхней границы функции, что означает верхнюю границу, до которой функция может расти. То есть ( ) = O( ( )), где ( ) ≤ c * ( ) для всех . Другими словами, ( ) растет так же быстро, как g( ).

Для алгоритма ( ) – это функция/метод, а n – размер входных данных. Часто можно увидеть, что мы описываем сложность алгоритма как O( log ), O( ) и т.д. Это означает, что сложность растет в зависимости от размера входных данных. Например, алгоритм быстрой сортировки имеет сложность O(n 2 ), что означает, что при удвоении размера входных данных (2n) количество итераций увеличится максимум в 4 раза ((2 ) 2 =4 2 ).

Как определить сложность?

Сложность бывает двух основных типов – пространственная и временная. Пространственная сложность – это объем памяти, занимаемый алгоритмом при выполнении; временная сложность – это время, необходимое для выполнения алгоритма. И пространство, и время важны для того, чтобы программы были эффективными, учитывая, что у компьютеров и у нас есть только ограниченные ресурсы, по крайней мере, пока.

Пространственная сложность

Как правило, пространственная сложность вызывает беспокойство только в рекурсивных функциях. В алгоритме без рекурсии количество переменных фиксировано, поэтому сложность равна O(1) , что означает, что пространственная сложность не растет с размером входных данных.

В случае, подобном этому:

Этот код на языке Python представляет собой

Возможно, более важной для алгоритма является временная сложность. Невозможно одновременно максимизировать временную и пространственную эффективность, но поскольку пространственная сложность обычно не идет дальше O(n), большинство вопросов, касающихся обозначения большого O, будет связано с временной сложностью.

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

Наиболее типичное использование циклов – это “поиск и сортировка”.

Сортировка вставкой:

Сортировка выбором:

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

Другим распространенным примером является рекурсия.

Посмотрите на следующий пример последовательности Фибоначчи:

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

Возможно, более важной для алгоритма является временная сложность. Невозможно одновременно максимизировать временную и пространственную эффективность, но поскольку пространственная сложность обычно не идет дальше O(n), большинство вопросов, касающихся обозначения большого O, будет связано с временной сложностью.

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

Наиболее типичное использование циклов – это “поиск и сортировка”.

Сортировка вставкой:

Сократите время выполнения цикла, изменив условия.

Если рекурсия не является обязательным условием, обобщите рекурсию для численных вычислений и используйте итерационный подход для экономии памяти.

• Использование другого метода для уменьшения глубины рекурсии
• Стиль преподавания Марко – интерактивный и ориентированный на общение; он фокусируется на мотивации студентов к активному обучению. Запишитесь на пробный урок с Марко прямо сейчас!
• Об учебном центре The Edge

Учебный центр The Edge является ведущим в Гонконге поставщиком услуг по подготовке к тестированию, академическому репетиторству и консультированию при поступлении. Основанный в 2008 году, The Edge помог тысячам студентов улучшить свои результаты по ACT и SAT, а также оценки по IB и AP. Команда AC только что завершила очередной успешный период, в ходе которого студенты были приняты в такие школы, как Колумбийский университет, Йель, UChicago и другие! Ознакомьтесь с нашими последними результатами приема!