Что такое асимптотика алгоритма

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

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

Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа:
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).

def bubble_sort(arr):
. . for j in xrange(0, N — 1):
. . . . for i in xrange(0, N — 1):
. . . . . . if(arr[i] > arr[i+1]):
. . . . . . . . tmp = arr[i]
. . . . . . . . arr[i] = arr[i+1]
. . . . . . . . arr[i+1] = tmp

Я намерено не ввожу проверку на наличие хотябы одного обмена (которая кстати не сказывается на O — сложности алгоритма), ради упрощения понимания сути.
Взглянув на код, сразу же обращаем внимание на вложеный цикл. О чем нам это говорит? Я надеюсь, что читатель знаком с основами программирования на любом языке (кроме функциональных, в которых циклы отсутствуют как таковые, а повторения реализуются рекурсией) и наглядно представляет себе, что такое вложеные циклы и как они работают. В данном примере, внешний цикл выполняется ровно n = 10 000 000 (т.к. наш массив состоит из 10 000 000 элементов) и столько же раз выполняется внутренний цикл, из этого очевидно следует, что общее кол-во итераций будет порядка n^2. Т.е. кол-во итераций зависит от размерности входных данных как ф-ия от n^2. Теперь, зная сложность алгоритма, мы можем проверить, насколько хорошо он будет работать в нашем случае. Подставив цифры в формулу n^2 получаем ответ 10 000 000 * 10 000 000 = 10 000 000 000 0000 итераций.
Хммм, впечатляет… В цикле у нас 3 комманды, предположим, что на выполнение каждой из них требуется 5 единиц времени (с1 = 5), тогда общее кол-во времени затраченного на сортировку нашего массива будет равно 5*f(n^2) (синяя кривая на рис.1).

рис.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, чем ф-ия отмеченная синим.

Теперь подумаем, хорошо ли это или плохо в нашем случае и можем ли мы заставить алгоритм работать эффективнее?
Как можно понять из графиков, приведенных на рис. 2, квадратичная ф-ия возрастает довольно быстро и при большом объеме входных данных, сортировка массива таким способом, может занять довольно длительное время, причем увеличение мощности процессора, будет сказываться лишь на коэффициенте c1, но сам алгоритм, по-прежнему будет принадлежать к классу алгоритмов с полиномиальной функцией роста O(n^2) (тут мы опять же используем определение (1.1) и подбираем такие c2 и N при которых с2*n^2 будет возрастать быстрее чем наша ф-ия c1*n^2 начиная с некоторого n >= N) и если в ближайшем будущем изобретут процессор, который будет сортировать наш массив всего за пару секунд, то при немного большем объеме входных данных, этот прирост в производительности будет полностью нивелирован кол-вом необходимых вычислений.
Таким же временным средством является решение реализовать алгоритм на низкоуровневом языке (например ассемблере), так как все, что мы сможем сделать – это, опять же, лишь немного уменьшить коэффициент c1 при этом все-равно оставаясь в классе сложности O(n^2).
А что будет, если вместо одноядерного процессора, мы будем использовать 4-х ядерный? На самом деле, результат изменится не сильно.
Разобьем наш массив на 4 части и каждую часть поручим выполнять отдельному ядру. Что мы получим? На сортировку каждой части понадобится ровно O((n / 4)^2). Так как все части сортируются одновременно, то этот результат и будет конечным временем сортировки четырех подмассивов, размерностью n/4. Возведем получившееся выражение в квадрат, получив таким образом сложность равную O(1/16*n^2 + n), где n — итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.
Поскольку анализ у нас асимптотический, то при достаточно больших n, ф-ия n^2 будет вносить гораздо больший вклад в итоговый результат, чем n и поэтому мы спокойно можем им пренебречь, как наиболее медленно возрастающем членом, также за малозначимостью принебрегаем коэффициентом 1/16 (см. (1.1)), что в итоге дает нам все тоже O(n^2).
Мы приходим к неутишительному выводу о том, что увеличением числа процессоров, равно как и повышение их частоты, не дают существенного прироста при данном алгоритме сортировки.

Что же можно сделать в этой ситуации, чтобы радикально ускорить сортировку? Необходимо, чтобы в худшем случае сложность алгоритма была меньше чем 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) и теоретически это было бы абсолютно верным утверждением, однако на практике такая оценка была бы лишена смысла.

• algorithms
• asymptotic analysis

О-символика

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

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

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

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

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

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

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

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

Логарифмическая функция — log n Линейная функция — an + b Квадратичная функция — an^2 + bn +c Степенная функция — an^z + . . . + an^2 + a*n^1 + a*n^0, где z — константа Показательная функция — a^n, где a — константа

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

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

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

Логарифм — log n Линейная функция — n Квадратичная функция — n^2 Степенная функция — n^z, где z — константа Показательная функция — a^n, где a — константа

О Большое

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

f(n) = 3log n + 100 g(n) = log n

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

3log n + 100 
Существуют ли константы c и n0, такие, что выражение верно для всех n > n0?
3log n + 100 2 (не определенно для n = 1)
Да! По определению О Большого f(n) является O(g(n)).
f(n) = 3 * n^2 g(n) = n
Является ли f(n) O(g(n))? Является ли 3 * n^2 O(n)? Посмотрим на определение О Большого:






3 * n^2 
Существуют ли константы c и n0, такие, что выражение верно для всех n > n0? Нет, не существуют. f(n) НЕ ЯВЛЯЕТСЯ O(g(n)).
Омега Большое
Омега Большое, записывается как Ω, — это асимптотическая запись для оценки лучшего случая, или для ограничения заданной функции снизу. Это позволяет сделать асимптотическую оценку нижней границы скорости роста времени выполнения алгоритма.
f(n) является Ω(g(n)), если существуют действительные константы c (c > 0) и n0 (n0 > 0), такие, что f(n) >= c g(n) для всех n > n0.
Примечание
Асимптотические оценки, сделаные при помощи О Большого и Омега Большого, могут как являться, так и не являться точными. Для того, чтобы обозначить, что границы не являются асимптотически точными, используются записи О Малое и Омега Малое.






О Малое
O Малое, записывается как о, — это асимптотическая запись для оценки верхней границы времени выполнения алгоритма при условии, что граница не является асимптотически точной.
f(n) является o(g(n)), если можно подобрать такие действительные константы, что для всех c (c > 0) найдётся n0 (n0 > 0), так что f(n) < c g(n) выполняется для всех n (n >n0).
Определения О-символики для О Большого и О Малого похожи. Главное отличие в том, что если f(n) = O(g(n)), тогда условие f(n) существует константа c > 0, но если f(n) = o(g(n)), тогда условие f(n) < c g(n) выполняется для всех констант c > 0.
Омега Малое
Омега Малое, записывается как ω, — это асимптотическая запись для оценки верхней границы времени выполнения алгоритма при условии, что граница не является асимптотически точной.






f(n) является ω(g(n)), если можно подобрать такие действительные константы, что для всех c (c > 0) найдётся n0 (n0 > 0), так что f(n) > c g(n) выполняется для всех n (n > n0).
Определения Ω-символики и ω-символики похожи. Главное отличие в том, что если 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 и n0 (c1 > 0, c2 > 0, n0 > 0) c1 g(n) < f(n) < c2 g(n) для всех n (n >n0).






∴ f(n) является Θ(g(n)) означает, что f(n) является O(g(n)) и f(n) является Ω(g(n)).
О Большое — основной инструмент для анализа сложности алгоритмов. Также см. примеры по ссылкам.
Заключение
Такую тему сложно изложить кратко, поэтому обязательно стоит пройти по ссылкам и посмотреть дополнительную литературу. В ней даётся более глубокое описание с определениями и примерами.
Дополнительная литература

  
Алгоритмы на Java
  
Алгоритмы. Построение и анализ

Ссылки

  
Оценки времени исполнения. Символ O()
  
Асимптотический анализ и теория вероятностей

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

  
Algorithms, Part I
  
Cheatsheet 1
  
Cheatsheet 2

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






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

Структуры данных: асимптотический анализ
Асимптотический анализ алгоритма — это определение математических границ/рамок его производительности во время выполнения, позволяющее очень легко находить время работы алгоритма в лучшем, среднем и худшем случае.
Асимптотический анализ связан c входными данными: если их нет, алгоритм работает за постоянное время. Все остальные факторы, кроме входных данных, считаются постоянными.
Асимптотический анализ имеет дело с вычислением времени выполнения любой операции в математических единицах. Так, если время выполнения одной операции вычисляется как f(n), а другой — как g(n2), значит, время выполнения первой операции по мере роста n увеличивается линейно, а второй — экспоненциально. И если значение n ничтожно мало, время выполнения обеих операций почти одинаково.
Обычно выделяют три времени выполнения алгоритма:







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

Асимптотические обозначения
Для расчета сложности времени выполнения алгоритма чаще используют следующие асимптотические обозначения:

  
Ο нотация;
  
Ω нотация;
  
θ нотация.

Нотация «O» большое , O
Обозначение Ο(n) — это формальный способ определения верхней границы времени выполнения алгоритма. Применяется для измерения временной сложности в худшем случае или наибольшего времени, требующегося для завершения алгоритма.
Например, для функции f(n)
Ο(f(n)) = g(n), где существует c > 0 и n0 такие, что f(n) ≤ c.g(n) для всех n > n0.>
Омега-нотация, Ω
Обозначение Ω(n) — это формальный способ определения нижней границы времени выполнения алгоритма. Применяется для измерения временной сложности в лучшем случае или наименьшего времени, требующегося для завершения алгоритма.






Например, для функции f(n)
Ω(f(n)) ≥ g(n), где существует c > 0 и n0 такие, что g(n) ≤ c.f(n) для всех n > n0.>
Тета-нотация, θ
Обозначение θ(n) — это формальный способ определения нижней и верхней границ времени выполнения алгоритма. Выглядит она так:
θ(f(n)) = g(n) тогда и только тогда, когда g(n) = Ο(f(n)) и g(n) = Ω(f(n)) для всех n > n0.>
Часто встречающиеся асимптотические обозначения
Вот список самых распространенных асимптотических обозначений:

Что такое «O» большое в программировании?
8 показателей эффективности классификации
6 принципов создания производительных веб-приложений

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

Ο (О-большое) – верхняя асимптотическая оценка роста временной функции;
Ω (Омега) – нижняя асимптотическая оценка роста временной функции;
Θ (Тета) – нижняя и верхняя асимптотические оценки роста временной функции.

Пусть n – величина объема данных. Тогда рост функции алгоритма f(n) можно ограничить функций g(n) асимптотически:



Обозначение
Описание


f(n) ∈ Ο(g(n))
f ограничена сверху функцией g с точностью до постоянного множителя


f(n) ∈ Ω(g(n))
f ограничена снизу функцией g с точностью до постоянного множителя


f(n) ∈ Θ(g(n))
f ограничена снизу и сверху функцией g



Например, время уборки помещения линейно зависит от площади этого самого помещения (Θ(S)), т. е. с ростом площади в n раз, время уборки увеличиться также в n раз. Поиск имени в телефонной книге потребует линейного времени Ο(n), если воспользоваться алгоритмом линейного поиска, либо времени, логарифмически зависящего от числа записей (Ο(log2(n))), в случае применения двоичного поиска.
Для нас наибольший интерес представляет Ο-функция. Кроме того, в последующих главах, сложность алгоритмов будет даваться только для верхней асимптотической границы.
Под фразой «сложность алгоритма есть Ο(f(n))» подразумевается, что с увеличением объема входных данных n, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n).
Важные правила асимптотического анализа:

O(k*f) = O(f) – постоянный множитель k (константа) отбрасывается, поскольку с ростом объема данных, его смысл теряется, например:

O(9,1n) = O(n)

O(f*g) = O(f)*O(g) – оценка сложности произведения двух функций равна произведению их сложностей, например:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2 )

O(f/g)=O(f)/O(g) – оценка сложности частного двух функций равна частному их сложностей, например:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

O(f+g) равна доминанте O(f) и O(g) – оценка сложности суммы функций определяется как оценка сложности доминанты первого и второго слагаемых, например:

O(n 5 +n 10 ) = O(n 10 )
Подсчет количества операций – дело утомительное и, что важно, совсем не обязательное. Исходя из выше перечисленных правил, чтобы определить сложность алгоритма, не нужно, как мы это делали прежде, считать все операции, достаточно знать какой сложностью обладает та или иная конструкция алгоритма (оператор или группа операторов). Так, алгоритм, не содержащий циклов и рекурсий, имеет константную сложность O(1). Сложность цикла, выполняющего n итераций, равна O(n). Конструкция их двух вложенных циклов, зависящих от одной и той же переменной n, имеет квадратичную сложность O(n 2 ).
Вот наиболее часто встречающиеся классы сложности:

O(1) – константная сложность;
О(n) – линейная сложность;
О(nа ) – полиномиальная сложность;
О(Log(n)) – логарифмическая сложность;
O(n*log(n)) – квазилинейная сложность;
O(2 n ) – экспоненциальная сложность;
O(n!) – факториальная сложность.



Похожие публикации:

Esp какой язык
Ooapb как пользоваться
Как узнать имя компьютера mac os
Кого лучше завести крысу или мышь