Asymptotic notation что это

Асимптотический анализ алгоритмов

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

Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа:
O(g(n)), &#937(g(n)), &#920(g(n)).
Давайте разбермся, что же это такое, но сначала я перечислю основные классы сложности применяемые при анализе:
f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост

Если раньше вы не встречались с подобными обозначениями, не переживайте, после прочтения этой статьи, все станет намного понятнее.
А начнем мы с символа O.

Сначала приведу формальное определение:
(1.1) Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).
Таким образом O – означает верхнее ограничение сложности алгоритма.

Давайте теперь попробуем применить это знание на практике.

Возьмем известную любому программисту задачу сортировки. Допустим нам необходимо отсортировать массив чисел, размерностью 10 000 000 элементов. Договоримся рассматривать худший случай, при котором для выполнения алгоритма понадобится наибольшее количество итераций. Не долго думая, мы решаем применять сортировку пузырьком как самую простую с точки зрения реализации.
Сортировка пузырьком позволяет отсортировать массив любой размерности без дополнительных выделений памяти. Вроде бы все прекрасно и мы с чистой совестью начинаем писать код (для примеров здесь и далее будет использоваться язык Python).

рис.1.
зеленая кривая соответствует графику ф-ии x^2 при c = 1, синия c = 5, красная c = 7

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

рис.2.
зеленая кривая соответствует графику ф-ии x^2 при c = 1, синия c = 5, красная c = 7

Возьмем c2 = 7. Мы видим, что новая ф-ия растет быстрее предыдущей (красная кривая на рис.2). Из определения (1.1), делаем вывод, что при с2 = 7 и n >= 0, g(n) = 7*n^2 всегда больше или равна ф-ии f(n) = 5*n^2, следовательно наша программа имет сложность O(n^2).
Кто не до конца понял это объяснение, посмотрите на графики ф-ий и заметьте, что ф-ия отмеченная на нем красным, при n >= 0 всегда имеет большее значение по y, чем ф-ия отмеченная синим.

Что же можно сделать в этой ситуации, чтобы радикально ускорить сортировку? Необходимо, чтобы в худшем случае сложность алгоритма была меньше чем O(n^2). Поразмыслив немного, мы решаем, что не плохо бы было, придумать такой алгоритм, сложность которого не превышает O(n), т.е. является линейной. Очевидно, что в случае O(n) скорость работы программы возрастет в N раз, так как вместо N^2 итераций, нам необходимо будет сделать всего лишь N. Прогнозируемый прирост скорости отлично виден на рис.3.

Серой прямой обозначена линейная сложность, а три кривых показывают сложность n^2 при различных коэффициентах c.

Но оказывается, что сделать сортировку со сложностью O(n) в общем случае просто не возможно (док-во)! Так на какую же сложность мы в лучшем случае можем расчитывать? Она равна O(n*log(n)), что является теоретически доказаным минимальным верхнем пределом для любого алгоритма сортировки основанного на сравнении элементов. Это конечно немного не то, чего мы ожидали получить, но все же это уже и не O(n^2). Осталось найти алгоритм сортировки удовлетворяющий нашим требованиям.
Покопавшись в интернете, видим, что им удовлетворяет «пирамидальная сортировка». Я не буду вдаваться в подробности алгоритма, желающие могут прочитать о нем самостоятельно на wiki, скажу только, что его сложность принадлежит классу O(n*log(n)) (т.е. максимально возможная производительность для сортировки), но при этом, он довольно труден в реализации.

Посмотрим на графики ниже и сравним скорости возрастания кол-ва вычислений для двух рассмотренных алгоритмов сортировки.

рис.4.

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

Остается открытым вопрос, целесообразно ли всегда предпочитать пирамидальную сортировку сортировке пузырьком?

рис.5.

Как видно на рис.5, при малых n, различия между двумя алгоритмами достаточно малы и выгода от использования пирамидальной сортировки — совсем незначительна, а учитывая, что «пузырек» реализуется буквально 5-6 строчками кода, то при малых n, он действительно является более предпочтительным с точки зрения умственных и временных затрат на реализацию 🙂

В заключении, чтобы более наглядно продемонстрировать разницу между классами сложности, приведу такой пример:
Допустим у нас етсь ЭВМ 45-ти летней давности. В голове сразу всплывают мысли о больших шкафах, занимающих довольно-таки обширную площадь. Допустим, что каждая команда на такой машине выполняется примерно за 10 миллисек. С такой скоростью вычислений, имея алгоритм сложности O(n^2), на решение поставленой задачи уйдет оооочень много времени и от затеи придется отказаться как от невыполнимой за допустимое время, если же взять алгоритм со сложностью O(n*log(n)), то ситуация в корне изменится и на расчет уйдет не больше месяца.

Посчитаем, сколько именно займет сортировка массива в обоих случаях

сверх-неоптимальный алгоритм (бывает и такое, но редко):
O(2^n) = оооооочень медленно, вселенная умрет, прежде чем мы закончим наш расчет…
пузырек:
O(n^2) = 277777778 часов (классический “пузырек”)
пирамидальная сортировка:
O(n*log(n)) = 647 часов (то чего мы реально можем добиться, применяя пирамидальную сортировку)
фантастически-эффективный алгоритм:
O(n) = 2.7 часов (наш гипотетический алгоритм, сортирующий за линейное время)
и наконец:
O(log(n)) = оооооочень быстро, жаль, что чудес не бывает…

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

Источник

Изучите X за Y минут

Где X=Asymptotic Notation

О-символика

Что это такое?

О-символика, или асимптотическая запись, — это система символов, позволяющая оценить время выполнения алгоритма, устанавливая зависимость времени выполнения от увеличения объёма входных данных. Она также известна как оценка сложности алгоритмов. Станет ли алгоритм невероятно медленным, когда объём входных данных увеличится? Будет ли алгоритм выполняться достаточно быстро, если объём входных данных возрастёт? О-символика позволяет ответить на эти вопросы.

Можно ли по-другому найти ответы на эти вопросы?

Один способ — это подсчитать число элементарных операций в зависимости от различных объёмов входных данных. Хотя это и приемлемое решение, тот объём работы, которого оно потребует, даже для простых алгоритмов делает его использование неоправданным.

Другой способ — это измерить, какое время алгоритм потребует для завершения на различных объёмах входных данных. В то же время, точность и относительность этого метода (полученное время будет относиться только к той машине, на которой оно вычислено) зависит от среды выполнения: компьютерного аппаратного обеспечения, мощности процессора и т.д.

Виды О-символики

В первом разделе этого документа мы определили, что О-символика позволяет оценивать алгоритмы в зависимости от изменения размера входных данных. Представим, что алгоритм — это функция f, n — размер входных данных и f(n) — время выполнения. Тогда для данного алгоритма f с размером входных данных n получим какое-то результирующее время выполнения f(n). Из этого можно построить график, где ось y — время выполнения, ось x — размер входных данных, а точки на графике — это время выполнения для заданного размера входных данных.

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

Виды функций, пределы и упрощения

Приведены несколько базовых функций, используемых при определении сложности в различных оценках. Список начинается с самой медленно возрастающей функции (логарифм, наиболее быстрое время выполнения) и следует до самой быстро возрастающей функции (экспонента, самое медленное время выполнения). Отметим, что в то время, как «n», или размер входных данных, возрастает в каждой из этих функций, результат намного быстрее возрастает в квадратичной, степенной и показательной по сравнению с логарифмической и линейной.

Крайне важно понимать, что при использовании описанной далее нотации необходимо использовать упрощённые выражения. Это означает, что необходимо отбрасывать константы и слагаемые младших порядков, потому что если размер входных данных (n в функции f(n) нашего примера) увеличивается до бесконечности (в пределе), тогда слагаемые младших порядков и константы становятся пренебрежительно малыми. Таким образом, если есть константа, например, размера 2^9001 или любого другого невообразимого размера, надо понимать, что её упрощение внесёт значительные искажения в точность оценки.

Т.к. нам нужны упрощённые выражения, немного скорректируем нашу таблицу…

О Большое

О Большое, записывается как О, — это асимптотическая запись для оценки худшего случая, или для ограничения заданной функции сверху. Это позволяет сделать асимптотическую оценку верхней границы скорости роста времени выполнения алгоритма. Пусть f(n) — время выполнения алгоритма, а g(n) — заданная временная сложность, которая проверяется для алгоритма. Тогда f(n) — это O(g(n)), если существуют действительные константы c (c > 0) и n₀, такие, что f(n) c g(n) выполняется для всех n, начиная с некоторого n₀ (n > n₀).

Является ли f(n) O(g(n))? Является ли 3 log n + 100 O(log n)? Посмотрим на определение О Большого:

Существуют ли константы c и n₀, такие, что выражение верно для всех n > n₀?

Да! По определению О Большого f(n) является O(g(n)).

Является ли f(n) O(g(n))? Является ли 3 * n^2 O(n)? Посмотрим на определение О Большого:

Существуют ли константы c и n₀, такие, что выражение верно для всех n > n₀? Нет, не существуют. f(n) НЕ ЯВЛЯЕТСЯ O(g(n)).

Омега Большое

Омега Большое, записывается как Ω, — это асимптотическая запись для оценки лучшего случая, или для ограничения заданной функции снизу. Это позволяет сделать асимптотическую оценку нижней границы скорости роста времени выполнения алгоритма.

f(n) является Ω(g(n)), если существуют действительные константы c (c > 0) и n₀ (n₀ > 0), такие, что f(n) >= c g(n) для всех n > n₀.

Примечание

Асимптотические оценки, сделаные при помощи О Большого и Омега Большого, могут как являться, так и не являться точными. Для того, чтобы обозначить, что границы не являются асимптотически точными, используются записи О Малое и Омега Малое.

О Малое

O Малое, записывается как о, — это асимптотическая запись для оценки верхней границы времени выполнения алгоритма при условии, что граница не является асимптотически точной.

f(n) является o(g(n)), если можно подобрать такие действительные константы, что для всех c (c > 0) найдётся n₀ (n₀ > 0), так что f(n) c g(n) выполняется для всех n (n > n₀).

Определения О-символики для О Большого и О Малого похожи. Главное отличие в том, что если f(n) = O(g(n)), тогда условие f(n) 0, но если f(n) = o(g(n)), тогда условие f(n) 0.

Омега Малое

Омега Малое, записывается как ω, — это асимптотическая запись для оценки верхней границы времени выполнения алгоритма при условии, что граница не является асимптотически точной.

f(n) является ω(g(n)), если можно подобрать такие действительные константы, что для всех c (c > 0) найдётся n₀ (n₀ > 0), так что f(n) > c g(n) выполняется для всех n (n > n₀).

Определения Ω-символики и ω-символики похожи. Главное отличие в том, что если f(n) = Ω(g(n)), тогда условие f(n) >= c g(n) выполняется, если существует константа c > 0, но если f(n) = ω(g(n)), тогда условие f(n) > c g(n) выполняется для всех констант c > 0.

Тета, записывается как Θ, — это асимптотическая запись для оценки асимптотически точной границы времени выполнения алгоритма.

f(n) является Θ(g(n)), если для некоторых действительных констант c1, c2 и n₀ (c1 > 0, c2 > 0, n₀ > 0) c1 g(n) f(n) c2 g(n) для всех n (n > n₀).

∴ f(n) является Θ(g(n)) означает, что f(n) является O(g(n)) и f(n) является Ω(g(n)).

О Большое — основной инструмент для анализа сложности алгоритмов. Также см. примеры по ссылкам.

Заключение

Такую тему сложно изложить кратко, поэтому обязательно стоит пройти по ссылкам и посмотреть дополнительную литературу. В ней даётся более глубокое описание с определениями и примерами.

Дополнительная литература

Ссылки

Ссылки (англ.)

Хотите предложить свой перевод? Может быть, улучшение перевода? Откройте Issue в репозитории Github или сделайте pull request сами!

Первоначально предоставлено автором Jake Prather, и обновлено 0 автором (-ами).

Источник

Введение в анализ сложности алгоритмов (часть 2)

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Сложность

Такой метод поиска значения внутри массива называется линейным поиском. Это обоснованное название, поскольку программа имеет f( n ) = n (что означает «линейный» более точно, мы рассмотрим в следующем разделе). Инструкция break позволяет программе завершиться раньше, даже после единственной итерации. Однако, напоминаю, что нас интересует самый неблагоприятный сценарий, при котором массив A вообще не содержит заданное значение. Поэтому f( n ) = n по-прежнему.

Давайте рассмотрим программу на Python, которая складывает два значения из массива и записывает результат в новую переменную:

Следующая программа на C++ проверяет, содержит ли вектор (своеобразный массив) A размера n два одинаковых значения:

Нотация «большое О»

В реальной жизни иногда проблематично выяснить точное поведение алгоритма тем способом, который мы рассматривали выше. Особенно для более сложных примеров. Однако, мы можем сказать, что поведение нашего алгоритма никогда не пересечёт некой границы. Это делает жизнь проще, так как чёткого указания на то, насколько быстр наш алгоритм, у нас может и не появиться, даже при условии игнорирования констант (как раньше). Всё, что нам нужно — найти эту границу, а как это сделать — проще объяснить на примере.

Наиболее известной задачей, которую используют при обучении алгоритмам, является сортировка. Даётся массив A размера n (звучит знакомо, не так ли?), и нас просят написать программу, его сортирующую. Интерес тут в том что, такая необходимость часто возникает в реальных системах. Например, обозревателю файлов нужно отсортировать файлы по имени, чтобы облегчить пользователю навигацию по ним. Или другой пример: в видеоигре может возникнуть задача сортировки 3D объектов, демонстрируемых на экране, по их расстоянию от точки зрения игрока в виртуальном мире. Цель: определить, какие из них будут для него видимы, а какие — нет (это называется Visibility Problem). Сортировка также интересна тем, что для неё существует множество алгоритмов, одни из которых хуже, чем другие. Так же эта задача проста для определения и объяснения. Поэтому давайте напишем кусок кода, который будет сортировать массив.

Перед вами совершенно неэффективный способ реализации сортировки массива на Ruby. (Конечно, Ruby поддерживает сортировку массивов с использованием встроенных функций, которые и следует использовать. Они несомненно быстрее, чем код выше, представленный исключительно для иллюстрации.)

Заметьте также, что хотя Ω и даёт нам нижний предел поведения нашей функции (т.е. мы улучшаем программу, чтобы она вычисляла меньшее количество инструкций), мы всё ещё ссылаемся на анализ наихудшего случая. Это происходит потому, что мы подаём на вход программы наихудший набор данных и анализируем её поведение.

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

Источник

Асимптотический анализ

В этой статье вы узнаете, что такое асимптотические нотации, познакомитесь с О-нотацией, нотациями Тета и Омега.

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

Производительность алгоритма может отличаться при работе с различными типами данных. С увеличением количества входных данных она также изменяется.

Асимптотический анализ — метод изучения производительности алгоритмов при различных объемах и типах входных данных.

Асимптотические нотации

Асимптотические нотации — это графики функций. Они служат для описания времени работы алгоритма, когда размер входных данных стремится к определенному значению или пределу.

Возьмем, к примеру, сортировку пузырьком. Когда массив, который мы вводим, уже отсортирован, время выполнения алгоритма линейно — это лучший случай.

Но если массив отсортирован в обратном порядке, то время выполнения будет максимальным (квадратичное). То есть, это худший случай.

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

В основном используются три нотации:

Большое «О»

Большое «О» — это верхняя граница скорости выполнения алгоритма. Эта нотация показывает скорость алгоритма в худшем случае.

Так как эта нотация дает нам представления о худшей скорости выполнения алгоритма, то ее анализ обязателен — нам всегда интересна эта характеристика.

Омега нотация (Ω-нотация)

Омега нотация — противоположность большому «О». Она показывает нижнюю границу скорости выполнения алгоритма. Она описывает лучший случай выполнения алгоритма.

Тета-нотация (Θ-нотация)

Тета-нотация объединяет в себе сразу две функции — верхнюю и нижнюю. Эта нотация отражает и верхнюю, и нижнюю границу скорости выполнения алгоритма. Именно поэтому она используется для анализа средней скорости выполнения алгоритма.

Для функции g(n) Θ(g(n)) задается следующим образом:

Источник

Learn X in Y minutes

Where X=Asymptotic Notation

Asymptotic Notations

What are they?

Asymptotic Notations are languages that allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases. This is also known as an algorithm’s growth rate. Does the algorithm suddenly become incredibly slow when the input size grows? Does it mostly maintain its quick run time as the input size increases? Asymptotic Notation gives us the ability to answer these questions.

Are there alternatives to answering these questions?

One way would be to count the number of primitive operations at different input sizes. Though this is a valid solution, the amount of work this takes for even simple algorithms does not justify its use.

Another way is to physically measure the amount of time an algorithm takes to complete given different input sizes. However, the accuracy and relativity (times obtained would only be relative to the machine they were computed on) of this method is bound to environmental variables such as computer hardware specifications, processing power, etc.

Types of Asymptotic Notation

In the first section of this doc, we described how an Asymptotic Notation identifies the behavior of an algorithm as the input size changes. Let us imagine an algorithm as a function f, n as the input size, and f(n) being the running time. So for a given algorithm f, with input size n you get some resultant run time f(n). This results in a graph where the Y-axis is the runtime, the X-axis is the input size, and plot points are the resultants of the amount of time for a given input size.

You can label a function, or algorithm, with an Asymptotic Notation in many different ways. Some examples are, you can describe an algorithm by its best case, worst case, or average case. The most common is to analyze an algorithm by its worst case. You typically don’t evaluate by best case because those conditions aren’t what you’re planning for. An excellent example of this is sorting algorithms; particularly, adding elements to a tree structure. The best case for most algorithms could be as low as a single operation. However, in most cases, the element you’re adding needs to be sorted appropriately through the tree, which could mean examining an entire branch. This is the worst case, and this is what we plan for.

Types of functions, limits, and simplification

These are some fundamental function growth classifications used in various notations. The list starts at the slowest growing function (logarithmic, fastest execution time) and goes on to the fastest growing (exponential, slowest execution time). Notice that as ‘n’ or the input, increases in each of those functions, the result increases much quicker in quadratic, polynomial, and exponential, compared to logarithmic and linear.

It is worth noting that for the notations about to be discussed, you should do your best to use the simplest terms. This means to disregard constants, and lower order terms, because as the input size (or n in our f(n) example) increases to infinity (mathematical limits), the lower order terms and constants are of little to no importance. That being said, if you have constants that are 2^9001, or some other ridiculous, unimaginable amount, realize that simplifying skew your notation accuracy.

Since we want simplest form, lets modify our table a bit…

Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of growth for a given function. It provides us with an asymptotic upper bound for the growth rate of the runtime of an algorithm. Say f(n) is your algorithm runtime, and g(n) is an arbitrary time complexity you are trying to relate to your algorithm. f(n) is O(g(n)), if for some real constants c (c > 0) and n₀, f(n) c g(n) for every input size n (n > n₀).

Is f(n) O(g(n))? Is 3 log n + 100 O(log n)? Let’s look to the definition of Big-O.

Is there some pair of constants c, n₀ that satisfies this for all n > n₀?

Yes! The definition of Big-O has been met therefore f(n) is O(g(n)).

Is f(n) O(g(n))? Is 3 * n^2 O(n)? Let’s look at the definition of Big-O.

Is there some pair of constants c, n₀ that satisfies this for all n > ₀? No, there isn’t. f(n) is NOT O(g(n)).

Big-Omega

Big-Omega, commonly written as Ω, is an Asymptotic Notation for the best case, or a floor growth rate for a given function. It provides us with an asymptotic lower bound for the growth rate of the runtime of an algorithm.

f(n) is Ω(g(n)), if for some real constants c (c > 0) and n₀ (n₀ > 0), f(n) is >= c g(n) for every input size n (n > n₀).

The asymptotic growth rates provided by big-O and big-omega notation may or may not be asymptotically tight. Thus we use small-o and small-omega notation to denote bounds that are not asymptotically tight.

Small-o

Small-o, commonly written as o, is an Asymptotic Notation to denote the upper bound (that is not asymptotically tight) on the growth rate of runtime of an algorithm.

f(n) is o(g(n)), if for all real constants c (c > 0) and n₀ (n₀ > 0), f(n) is c g(n) for every input size n (n > n₀).

The definitions of O-notation and o-notation are similar. The main difference is that in f(n) = O(g(n)), the bound f(n) 0, but in f(n) = o(g(n)), the bound f(n) 0.

Small-omega

Small-omega, commonly written as ω, is an Asymptotic Notation to denote the lower bound (that is not asymptotically tight) on the growth rate of runtime of an algorithm.

f(n) is ω(g(n)), if for all real constants c (c > 0) and n₀ (n₀ > 0), f(n) is > c g(n) for every input size n (n > n₀).

The definitions of Ω-notation and ω-notation are similar. The main difference is that in f(n) = Ω(g(n)), the bound f(n) >= g(n) holds for some constant c > 0, but in f(n) = ω(g(n)), the bound f(n) > c g(n) holds for all constants c > 0.

Theta

Theta, commonly written as Θ, is an Asymptotic Notation to denote the asymptotically tight bound on the growth rate of runtime of an algorithm.

f(n) is Θ(g(n)), if for some real constants c1, c2 and n₀ (c1 > 0, c2 > 0, n₀ > 0), c1 g(n) is f(n) is c2 g(n) for every input size n (n > n₀).

∴ f(n) is Θ(g(n)) implies f(n) is O(g(n)) as well as f(n) is Ω(g(n)).

Feel free to head over to additional resources for examples on this. Big-O is the primary notation use for general algorithm time complexity.

Endnotes

It’s hard to keep this kind of topic short, and you should go through the books and online resources listed. They go into much greater depth with definitions and examples. More where x=‘Algorithms & Data Structures’ is on its way; we’ll have a doc up on analyzing actual code examples soon.

Books

Online Resources

Got a suggestion? A correction, perhaps? Open an Issue on the Github Repo, or make a pull request yourself!

Originally contributed by Jake Prather, and updated by 8 contributor(s).

Источник