Асимптотика как вычислить
Перейти к содержимому

Асимптотика как вычислить

  • автор:

На одной асимптотике далеко не уедешь…

При выборе алгоритма часто говорят об асимптотике того или иного решения задачи. При этом можно встретить высказывания, что, мол, «вот этот» алгоритм работает за O(n), а «вон тот» – за O(n·log(n)), значит первый однозначно лучше. Либо раз оба метода работают за O(n²), значит их можно считать равнозначными, и обсуждать, чем один может быть лучше другого, большого смысла нет.

Лично я не могу согласиться с таким мнением, по крайней мере, когда речь идёт в контексте программирования, поэтому решил написать данную статью и поделиться некоторыми мыслями о возможных нюансах.

Как вам такое?

  1. Не стоит забывать, что операции, которые можно принять за O(1), бывают очень простые (сложение/вычитание), а бывают весьма навороченные (многоэтажные формулы со сложными функциями). Операции деления, вычисления тригонометрических и логарифмических функций, степеней (включая корни) и т.п., особенно с вещественными числами, выполняются в разы (а иногда в десятки и сотни раз медленнее), чем операции сложения, вычитания и умножения, особенно с целыми числами. Таким образом, даже O(1) в разных алгоритмах могут отличаться на порядки.
  2. Даже если сложность операций примерно одинакова и их количество, на первый взгляд, примерно то же, реальное число операций может существенно различаться. К примеру, один алгоритм проходит по всему массиву, другой – лишь по его части (которая формально может быть любой длины, однако на практике довольно коротка, скажем, 1/10 от длины массива). А если такое происходит ещё и во вложенном цикле, то мы получим реальную разницу в скорости в 100 раз. Кроме того, если вы помните, константы при определении асимптотической сложности, не учитываются. Т.е. даже если вы обернёте ваш алгоритм в цикл на 1 млн итераций, то ваше «O» не изменится, по факту же скорость упадёт примерно на 6 десятичных порядков. На практике такое, конечно, вряд ли можно встретить, но алгоритмов, в которых проход по одному и тому же массиву осуществляется несколько раз (либо происходит несколько операций сортировки, повторяющиеся вложенные циклы и пр.), предостаточно. Да и, скажем, log(n) может означать как log2(n), так и log10(n), разница между которыми примерно в 3.32 раза.
  3. Не забывайте, что кроме скорости есть и другие важные параметры, например, объём используемой памяти. Поэтому алгоритм, работающий за O(n²) в отдельных случаях может быть более предпочтительным, чем алгоритм, работающий за O(n) или O(n·log(n)), но использующий значительный объём памяти. Количество используемых элементов памяти также может оцениваться с помощью «O», и при оценке сложности алгоритма неплохо бы писать рядом и оценку использования памяти.
  4. Некоторые из алгоритмов могут потребовать предварительной подготовки (и, опять же, памяти), а некоторые – нет. Хороший пример – тест простоты числа. Его можно реализовать множеством способов, но рассмотрим и сравним лишь 2 из них: метод перебора (сложностью около O(sqrt(n)) операций деления) и с помощью решета Эратосфена или Аткина (тест простоты выполняется за O(1), но с предварительной подготовкой массива порядка O(n·log(log(n))) или O(n/log(log(n))) соответственно). Использование памяти для последнего алгоритма можно соптимизировать как минимум до 32 мегабайта на 1 млрд чисел (т.е. до 1 байта на 30 чисел), причём эти значения можно даже не вычислять при каждом запуске программы, а закэшировать, сохранив на диске. Какой из способов предпочесть – сильно зависит от конкретного случая использования, иногда гораздо более предпочтительным окажется тест Миллера или Миллера-Рабина. Кстати, тест простоты методом перебора – неплохой пример того, что в зависимости от исходного значения (n) работа алгоритма может завершиться как на первых итерациях (чётное число или число, кратное 3, 5, 7), так и выполняться довольно приличное время (большое простое число), хотя формально его сложность, как я уже говорил, составляет O(sqrt(n)). Кому интересно, вот «здесь» я приводил простые методы алгоритмического ускорения теста простоты только лишь для одного метода перебора с реализацией на C++. А вот «здесь» есть пример реализации метода Миллера на Python.
  5. Важен не только сам алгоритм, но и его реализация. Один и тот же алгоритм может различаться по скорости в сотни раз просто из-за выбора разных языков программирования. Алгоритм, работающий, скажем, за O(n·log(n)) на C/C++ может оказаться ощутимо быстрее, чем работающий за O(n) на Python, причём для довольно больших n. Кроме того, есть множество нюансов оптимизации, применительно к платформе, формату хранения данных, ветвлению, реализации функций стандартных библиотек и пр. К примеру, если один алгоритм позволяет оптимизировать работу с кэшем процессора, использовать SIMD или многопоточную работу, а другой – нет, скорость может отличаться в разы или даже в десятки раз (при том, что всё остальное примерно одинаково). Последовательная работа с массивом, расположенным в памяти единым блоком, только лишь из-за специфики его организации быстрее, чем со связным списком (разумеется, если не рассматривать вставку элементов в начало или в середину массива/списка). Кэширование данных, полученных на предыдущих итерациях (например, в рекурсивных алгоритмах) могут увеличить скорость на много порядков. И т.д. Кто-то ехидно воскликнет: «К чему это всё? Мы же обсуждаем сами алгоритмы, а не их реализацию!» К тому, что некоторые алгоритмы позволяют без труда реализовать хорошую оптимизацию, иные же усложняют этот процесс или даже делают какую-то оптимизацию невозможной. Я не призываю к преждевременной оптимизации, однако не зря же специалисты по высокопроизводительным системам говорят: «При написании таких систем, над производительностью системы приходится думать уже на этапе архитектуры и дизайна системы, еще до того, как написана хоть одна строчка кода» (цитата из статьи по ссылке выше).

Если подумать ещё, наверняка можно найти и другие нюансы, но по-моему, и этого уже достаточно, чтобы хорошенько задуматься: действительно ли «O» – единственный важный показатель скорости алгоритма?

Неужели разница в скорости в 2, 5, 10 раз ничего не значит? Почему же большинство людей предпочитают быстрые SSD, нежели медленные HDD? Ведь алгоритмы копирования везде одинаковые (по крайней мере, лично я больше чем O(n) пока не встречал) 🙂

А представьте, какова может быть разница, если просуммировать все эти нюансы! Некоторые алгоритмы с бóльшим «O» могут работать чуть быстрее, чем иные с меньшим «O» (по меньшей мере, для относительно небольших n… кстати, а всегда ли n должно стремиться к бесконечности при оценке скорости алгоритма?)

Практический пример

В качестве конкретного примера приведу методы сортировки массивов. Многие думают, что методы сортировки пузырьком и вставками примерно одинаковы по скорости (поскольку сложность обоих составляет O(n²)). Однако я не раз убеждался на практике, что сортировка вставками работает почти на порядок быстрее. Для иллюстрации этого некоторое время назад я сделал небольшой сравнительный тест нескольких методов сортировки (ниже в комментариях выложены результаты теста на моём компьютере, соотношение скорости сортировки пузырьком и вставками указано в строке «Bubble/insertion sort time ratio»).

Кроме того, алгоритм быстрой сортировки (который тоже имеет множество реализаций, ощутимо различающихся как по скорости, так и по глубине рекурсии) может модифицироваться таким образом, что при достижении некоторого порога размера массивов, на которые происходит деление исходного массива (например, когда элементов становится меньше 16-ти; а иногда ещё и при достижении определённой глубины рекурсии), сортировка переключается на… сортировку вставками (либо дальнейшая быстрая сортировка прекращается, а сортировка вставками применяется уже позже ко всему не до конца отсортированному массиву). Казалось бы, зачем это делается, ведь сортировка вставками значительно медленнее быстрой сортировки? Однако на практике оказывается, что сортировка небольших массивов зачастую происходит чуть быстрее именно «вставками», нежели «быстрым» методом («quick/quick-insertion sort time ratio» в том же тесте по ссылке выше). Даже в тех случаях, когда скорость обоих методом примерно равная, глубина рекурсии уменьшается.

Вывод

Какой вывод можно сделать из всего этого? Очень простой: теория – это хорошо, но она должна подкрепляться практикой и знаниями возможных подводных камней. Как гласит японская пословица, знание является наградой за действие.

Эпилог

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

Разумеется, при бесконечно больших объёмах данных (n → ∞) асимптотическая оценка сложности будет как нельзя лучше отражать характер роста времени работы алгоритмов. И никакие доводы, что «сложение быстрее деления» или что «константа всё же имеет значение» не будут столь важны, как эта оценка. Однако в реальной жизни не все так идеально, как в математике, и объём данных почти всегда ограничен (причём, нередко довольно небольшими величинами). А это значит, что есть смысл брать во внимание и другие параметры и оценить реальную эффективность с учётом этих параметров и возможных диапазонов величины n. Но и здесь важно трезво смотреть на ситуацию: не вырастет ли «завтра» это n на порядок, к примеру, в связи с технологическим ростом или ростом бизнеса? Может быть, действительно есть смысл использовать алгоритм, который сейчас работает в 1.5 раза медленнее, но через месяц окажется в 2 раза быстрее, а через год – в 5? Или даже сделать 2 алгоритма и динамически выбирать между ними в зависимости от объёма входных данных! По этому поводу мне вспомнилась история с катастрофой на Ariane 5.

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

Ключевые идеи статьи:

  1. Если вам важна скорость, то при выборе алгоритма с одинаковой асимптотикой (скорости работы и объёма требуемой памяти) обращайте внимание на другие характеристики, которые могут существенно влиять на скорость (различаясь в разы или даже порядки) и проводите тесты. В некоторых случаях довольно похожие алгоритмы с одинаковой сложностью и схожими операциями, как в моём примере про сортировку пузырьком и вставками, могут существенно отличаются по скорости (кстати, вот ссылка на ещё один тест алгоритмов сортировки, уже не мой).
  2. Небольшие отличия в оценке асимптотической сложности могут перекрываться другими нюансами (в т.ч. описанными выше). К примеру, логарифм часто можно принять за константу (поскольку, к примеру, log2(1’048’576) = 20, а log2(1’073’741’824) = 30), поэтому в случае O(n) и O(n·log(n)) есть смысл сравнить реальную эффективность алгоритмов даже при значительных n. Если же оценка существенна: O(n) и O(n²), то первый алгоритм, разумеется, почти всегда будет быстрее уже при довольно незначительном объёме входных данных.
  • алгоритмы
  • асимптотика
  • оценка скорости

асимптотика — Найти асимптотику

Все эти примеры однотипны. Используйте формулы для разложения основных элементарных функций. Например, $%\sqrt[5]=(1+x^2)^a$% при $%a=\frac15$%, и так далее.

(3 Окт ’15 0:10) falcao

Здравствуйте

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

задан
3 Окт ’15 0:05

показан
1096 раз

обновлен
3 Окт ’15 0:10

Асимптотика как вычислить

МЕРОПРИЯТИЯ

Всероссийский хакатон по биометрии

Комментарии

Популярные По порядку
Не удалось загрузить комментарии.

ВАКАНСИИ

Преподаватель на курс БД SQL в Proglib.Academy
по итогам собеседования

Методист-педагогический дизайнер в Proglib.Academy
по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

10 структур данных, которые вы должны знать (+видео и задания)

Бо Карнс – разработчик и преподаватель расскажет о наиболее часто используемых и общих структурах данных. Специально для вас мы перевели его статью.

Какие алгоритмы нужно знать, чтобы стать хорошим программистом?

Данная статья содержит не только самые распространенные алгоритмы и структуры данных, но и более сложные вещи, о которых вы могли не знать. Читаем и узнаем!

Изучаем алгоритмы: полезные книги, веб-сайты, онлайн-курсы и видеоматериалы

В этой подборке представлен список книг, веб-сайтов и онлайн-курсов, дающих понимание как простых, так и продвинутых алгоритмов.

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

Пусть последовательность [math]a_0, a_1, \ldots[/math] положительных чисел такова, что [math]\cfrac>=A\cfrac + \ldots + \alpha_k>+ \ldots +\beta_k>[/math] для всех достаточно больших [math]n[/math] , причем [math]\alpha_1 \ne \beta_1[/math] . Тогда [math]a_n[/math] растет как [math]a_n \sim c \cdot A^n \cdot n^[/math] для некоторой постоянной [math]c\gt 0[/math] .

Замечание: Предположения леммы не позволяют определить величину константы [math]c[/math] . Действительно, умножив последовательность [math]a_n[/math] на произвольную постоянную [math]d \gt 0[/math] , мы получим новую последовательность с тем же отношением последовательных членов, константа [math]c[/math] для которой увеличивается в [math]d[/math] раз.

Рассмотрим предел [math]\lim\limits_ >>[/math] . При [math]a_n \sim c \cdot A^n \cdot n^[/math] для некоторого [math]c[/math] данный предел будет существовать и равен [math]c[/math] . С другой стороны, из определения существования предела [1] на бесконечности следует, что он равен некоторому [math]c[/math] , то есть [math]\lim\limits_ >> = c[/math] . Из чего можно сделать вывод, что утверждение леммы эквивалентно тому, что существует предел [math]\lim\limits_ >>[/math] .
Прологарифмировав, мы приходим к необходимости доказать существование предела [math]\lim\limits_ <( \ln — n \cdot \ln A — (\alpha_1 — \beta_1) \cdot \ln n )>[/math] .

Для доказательства существования предела применим критерий Коши [2] , т. е. будем доказывать, что рассматриваемая последовательность фундаментальна [3] .

Перепишем отношение [math]\cfrac>[/math] в виде

Прологарифмировав отношение [math]\cfrac>[/math] , получаем

[math]\ln a_ — \ln a_n = \ln A + \ln f\left(\cfrac\right)[/math] .

Посмотрим на функцию [math]\ln f(x)[/math] . Выпишем начальные члены разложения функции [math]f[/math] в ряд в точке [math]0[/math] :

[math]f(x)=1 + (\alpha_1 — \beta_1) \cdot x + \gamma \cdot x^2 + \ldots [/math] для некоторой константы [math]\gamma[/math] . Это разложение — самый существенный элемент доказательства. Именно коэффициент [math]\alpha_1 — \beta_1[/math] (отличный от нуля по предположению леммы) при линейном члене указывает на присутствие сомножителя [math]n^[/math] в асимптотике. Для логарифма функции [math]f[/math] имеем

[math]\ln f(x)=(\alpha_1-\beta_1) \cdot x+\tilde <\gamma>\cdot x^2 + \ldots[/math]

Поэтому для некоторой постоянной [math]C[/math] при достаточно маленьком [math]x[/math] имеем [math]|\ln f(x) — (\alpha_1 — \beta_1) \cdot x|\lt C \cdot x^2[/math] . В частности, если [math]N[/math] достаточно велико, то [math]∀ n\gt N[/math] получаем систему [math](*)[/math]

[math] \begin \begin \left| \ln a_ — \ln a_n — \ln A — (\alpha_1 — \beta_1) \cdot \cfrac \right| \lt C \cdot \cfrac, \\ \left| \ln a_ — \ln a_ — \ln A — (\alpha_1 — \beta_1) \cdot \cfrac \right| \lt C \cdot \cfrac, \\ \ldots \\ \left| \ln a_ — \ln a_ — \ln A — (\alpha_1 — \beta_1) \cdot \cfrac \right| \lt C \cdot \cfrac. \\ \end \end [/math]

Теперь интересующее нас выражение в левой части неравенства [math]|\ln a_ — \ln a_n — m \cdot \ln A — (\alpha_1 — \beta_1) \cdot \ln <(n + m)>+ (\alpha_1 — \beta_1) \cdot \ln n| \lt ε [/math] можно оценить с помощью системы [math](*)[/math] и неравенства треугольника [4] :

[math]\left| \ln a_ — \ln a_n — m \cdot \ln A — (\alpha_1 — \beta_1) \cdot ( \ln — \ln n) \right| =[/math]

[math]= | \ln a_ — \ln a_ + \ln a_ — \ldots + \ln a_ — \ln a_n — m \cdot \ln A — [/math]

[math] — (\alpha_1 — \beta_1) \cdot \sum\limits_^ \cfrac + (\alpha_1 — \beta_1) \cdot \sum\limits_^ \cfrac — (\alpha_1 — \beta_1) \cdot (\ln — \ln n) \Bigg| \leqslant[/math]

[math]\leqslant \left| \ln a_ — \ln a_n — \ln A — (\alpha_1 — \beta_1) \cdot \cfrac \right| + \left| \ln a_ — \ln a_ — \ln A — (\alpha_1 — \beta_1) \cdot \cfrac \right| +[/math]

[math]+ \left| \ln a_ — \ln a_ — \ln A — (\alpha_1 — \beta_1) \cdot \cfrac \right| + \left| \alpha_1 — \beta_1 \right| \cdot \left| \sum\limits_^ \cfrac — \ln + \ln n \right| \leqslant[/math]

[math]\leqslant C \cdot \left(\cfrac + \cfrac + \ldots + \cfrac\right) + \left| \alpha_1 — \beta_1 \right| \cdot \left| \sum\limits_^ \cfrac — \ln + \ln n \right|[/math] .

Поскольку ряд [math]\sum\limits_^ <\infty>\cfrac[/math] сходится, первое слагаемое в правой части последнего неравенства при больших [math]n[/math] можно сделать сколь угодно малым. Чтобы оценить второе слагаемое, заметим, что стоящая в нем сумма представляет собой площадь под графиком ступенчатой функции [math]\cfrac[/math] на отрезке [math][n, n+m][/math] ,

График функции [math]y = \cfrac<1>[/math] на отрезке [math][n, n + m][/math]

(Здесь через [math][x][/math] обозначена целая часть числа [math]x[/math] , наибольшее целое число, не превосходящее [math]x[/math] .) Эта площадь больше, чем площадь под графиком функции [math]y = \cfrac[/math] , но меньше, чем площадь под графиком функции [math]y = \cfrac[/math] на этом же отрезке. Площадь под графиком функции [math]\cfrac [/math] равна [math]\ln <(n + m)>— \ln [/math] , площадь под графиком функции [math]y = \cfrac[/math] равна [math]\ln — \ln [/math] . Таким образом, интересующая нас разность не превосходит [math]\left| (\ln — \ln ) — \left( \ln — \ln n \right) \right| =[/math]

Примеры

Пример. Рассмотрим производящую функцию для чисел Каталана

[math]A(s) = 1 + s + 2 \cdot s^2 + 5 \cdot s^3 + \ldots [/math]

Возведя ее в квадрат и умножив результат на s, получим

[math]s \cdot A^2(s) = s + 2 \cdot s^2 + 5 \cdot s^3 + 14 \cdot s^4 + \ldots = A(s) — 1[/math] ,

что дает нам квадратное уравнение на производящую функцию

[math]s \cdot A^2(s) — A(s) + 1 = 0,[/math]

Второй корень уравнения отбрасывается, так как [math]\cfrac > = \cfrac + \ldots[/math] содержит отрицательные степени [math]s[/math]

Найденная производящая функция позволяет найти явную форму для чисел Каталана. Согласно биному Ньютона [5]

[math]a_n = \cfrac \cdot \cfrac \cdot \cfrac \cdot \ldots \cdot \cfrac \cdot 4^>,[/math]

откуда, умножая на числитель и знаменатель на [math]n![/math] и сокращая на [math]2^[/math] , получаем

Последняя формула дает и более простое рекурсивное соотношение для чисел Каталана:

Поэтому [math]c_n \sim c \cdot 4^n \cdot n^>[/math] для некоторой постоянной [math]c[/math] .

Пример. Найдем асимптотику коэффициентов для функции [math](a-s)^[/math] , где [math]\alpha[/math] вещественно. В ряде случаев эта асимптотика нам уже известна, например, при [math]\alpha=−1[/math] . Согласно определению функции [math](1-s)^[/math] имеем

Если [math]\alpha[/math] — целое неотрицательное число, то ряд обрывается и вопроса об асимптотике не возникает. В противном случае, начиная с некоторого номера, все коэффициенты ряда имеют одинаковый знак. Для определения асимптотики мы можем воспользоваться леммой при [math]a_n=(-1)^n \cdot \cfrac^n>:[/math]

Поэтому [math]a_n \sim c \cdot a^ \cdot n^[/math] . Например, коэффициенты функции [math]-(1-4 \cdot s)^>[/math] ведут себя как [math]c \cdot 4^n \cdot n^>[/math] , и мы получаем повторный вывод ассимптотики для чисел Каталана.

См. также

  • Производящая функция
  • Числа Каталана

Примечания

  1. ↑Предел числовой последовательности
  2. ↑Критерий Коши
  3. ↑Фундаментальная последовательность
  4. ↑Неравенство треугольника
  5. ↑Бином Ньютона

Источники информации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *