Нотация Big O: Что это такое?

Первоначально опубликовано на Towards AI – ведущей в мире компании, специализирующейся на новостях и СМИ в области ИИ и технологий. Если вы создаете продукт или услугу, связанную с ИИ, мы приглашаем вас рассмотреть возможность стать спонсором ИИ. В Towards AI мы помогаем масштабировать стартапы в области ИИ и технологий. Позвольте нам помочь вам вывести вашу технологию в массы.

Программирование

Обратите внимание, что при оценке сложности алгоритма константы не учитываются, поскольку они не оказывают существенного влияния на количество операций (когда (n ) становится очень большим). Например, если алгоритм выполняется в порядке n2, замените n на cn, чтобы указать, что алгоритм выполняется в порядке c2n2, а в нотации big O константа c2 игнорируется. Например, если время выполнения алгоритма равно O (n) при измерении по количеству цифр n входного числа x, то при измерении как функции входного числа время его выполнения равно O (log x). x, потому что n = O ( log x).

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

В вычислениях нотация Big O используется для классификации алгоритмов на основе того, как время их выполнения или требования к пространству растут по мере увеличения размера входных данных. Большая O-нотация – это математическая нотация, используемая для классификации алгоритмов на основе того, как время их выполнения или требования к пространству растут по мере увеличения размера входных данных. Нотация Big O также используется для обозначения сложности пространства, которая работает аналогичным образом: сколько пространства использует алгоритм, поскольку n увеличивает зависимость между увеличением размера входных данных и увеличением требуемого пространства.

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

На диаграмме ниже показана сложность Big-O, упомянутая выше, и количество элементов на входе в зависимости от количества операций. Сложность напрямую связана с размером входных данных: алгоритм делает дополнительный шаг для каждого дополнительного элемента данных. Эти алгоритмы сильно влияют на производительность каждого дополнительного входного элемента.

Алгоритм с квадратичной временной сложностью имеет плохую масштабируемость: если увеличить размер входных данных в 10 раз, то время увеличится в 100 раз. На самом деле, временная сложность Th (n log n) очень близка к линейной: Для решения задачи вдвое большего размера требуется примерно вдвое больше времени. Вместо этого мы можем думать о времени как о количестве операций или шагов, необходимых для решения задачи размерности n. Другими словами, нотация Big-O – это способ отслеживания того, как быстро растет время выполнения относительно размера входных данных. Таким образом, мы можем сказать, что время выполнения растет “на порядок больше размера входных данных” (O (n)) или на “порядок квадрата размера входных данных” (O (n2)).

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

Это часто называют “постоянным временем”. Если вы можете создать алгоритм для решения проблемы за O (1), то вы, вероятно, на верном пути. Некоторые алгоритмы, такие как сортировка корзины, имеют пространственную сложность O (n), но могут уменьшить временную сложность до O (1). Например, сортировка выбором имеет пространственную сложность O (1), потому что она хранит только минимальное значение и его индекс для сравнения, максимально используемое пространство не увеличивается с размером входа.

Например, временная сложность для сортировки по выбору может быть определена функцией f (n) = n2 / 2-n / 2, как обсуждалось в предыдущем разделе. Мы можем упростить это уравнение, исключив константы и все недоминирующие члены. Когда вы вычисляете большую сложность чего-либо, вы просто устраняете постоянные члены.

Вообще говоря, постоянная величина 1 довольно незначительна по сравнению со значением переменной n. Тогда мы просто сократим приведенное выше выражение до O (n) и получим Big-O print_values runtime. В отличие от O (N), которое требует дополнительного шага для каждого элемента данных, O (log N) означает, что алгоритм делает дополнительный шаг каждый раз, когда данные удваиваются.

Этот быстрый снимок показывает, как производительность первого алгоритма зависит от значения n. Чем больше число, тем больше шагов должен выполнить алгоритм. Обычно, когда вы интересуетесь нотацией алгоритма Big-O, вас больше интересует общая производительность, а не точный анализ количества шагов. Чтобы упростить нотацию, мы можем указать только значение эффективности.

Эта запись позволит вам измерить скорость роста вашего алгоритма по отношению к входным данным. Она описывает наихудший случай производительности вашего кода. Ниже приведена шпаргалка по временной и пространственной сложности типичных алгоритмов.

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

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

Нотация Big O: What Is It? была первоначально опубликована в Towards AI на Medium, где люди продолжают разговор, выделяя и отвечая на эту статью.

Присоединяйтесь к тысячам лидеров в области данных в информационном бюллетене Towards AI. Это бесплатно, мы не рассылаем спам и никогда не сообщаем ваш адрес электронной почты. Будьте в курсе последних событий в области ИИ. От исследований до проектов и идей. Если вы создаете стартап в области ИИ, продукт, связанный с ИИ, или услугу, мы приглашаем вас рассмотреть возможность стать спонсором.