From eb2bd9e81266dcfa23867907dc00f05711807b7e Mon Sep 17 00:00:00 2001 From: pru-mike Date: Wed, 15 Mar 2017 12:07:05 +0300 Subject: [asymptotic-notation/ru] Added russian translation (#2679) --- ru-ru/asymptotic-notation-ru.html.markdown | 225 +++++++++++++++++++++++++++++ 1 file changed, 225 insertions(+) create mode 100644 ru-ru/asymptotic-notation-ru.html.markdown (limited to 'ru-ru/asymptotic-notation-ru.html.markdown') diff --git a/ru-ru/asymptotic-notation-ru.html.markdown b/ru-ru/asymptotic-notation-ru.html.markdown new file mode 100644 index 00000000..73ad80ba --- /dev/null +++ b/ru-ru/asymptotic-notation-ru.html.markdown @@ -0,0 +1,225 @@ +--- +category: Algorithms & Data Structures +name: Asymptotic Notation +contributors: + - ["Jake Prather", "http://github.com/JakeHP"] + - ["Divay Prakash", "http://github.com/divayprakash"] +translators: + - ["pru-mike", "http://gihub.com/pru-mike"] +lang: ru-ru +--- + +# О-cимволика + +## Что это такое? + +О-cимволика или асимптотическая запись это система символов позволяющая оценить +время выполнения алгоритма, устанавливая зависимость времени выполнения от +увеличения объема входных данных, так же известна как оценка +сложности алгоритмов. Быстро-ли алгоритм станет невероятно медленным, когда +объем входных данных увеличится? Будет-ли алгоритм выполняться достаточно быстро, +если объем входных данных возрастет? О-символика позволяет ответить на эти +вопросы. + +## Можно-ли по-другому найти ответы на эти вопросы? + +Один способ это подсчитать число элементарных операций в зависимости от +различных объемов входных данных. Хотя это и приемлемое решение, тот объем +работы которого оно потребует, даже для простых алгоритмов, делает его +использование неоправданным. + +Другой способ это измерить какое время алгоритм потребует для завершения на +различных объемах входных данных. В тоже время, точность и относительность +(полученное время будет относиться только к той машине на которой оно +вычислено) этого метода зависит от среды выполнения: компьютерного аппаратного +обеспечения, мощности процессора и т.д. + +## Виды О-символики + +В первом разделе этого документа мы определили, что О-символика +позволяет оценивать алгоритмы в зависимости от изменения размера входных +данных. Представим что алгоритм это функция f, n размер входных данных и +f(n) время выполнения. Тогда для данного алгоритма f c размером входных +данных 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)), если +существуют действительные константы с (с > 0) и n0, такие +что `f(n)` <= `c g(n)` выполняется для всех n начиная с некоторого n0 (n > n0). + +*Пример 1* + +``` +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 * log n +``` + +Существуют-ли константы c, n0 такие что выражение верно для всех n > n0 + +``` +3log n + 100 <= 150 * log n, n > 2 (неопределенно для n = 1) +``` + +Да! По определению О-Большого `f(n)` является O(g(n)). + +*Пример 2* + +``` +f(n) = 3 * n^2 +g(n) = n +``` + +Является-ли `f(n)` O(g(n))? +Является-ли `3 * n^2` O(n)? +Посмотрим на определение О-Большого: + +``` +3 * n^2 <= c * n +``` + +Существуют-ли константы c, n0 такие что выражение верно для всех n > n0? +Нет, не существуют. `f(n)` НЕ ЯВЛЯЕТСЯ O(g(n)). + +### Омега-Большое +Омега-Большое, записывается как **Ω**, это асимптотическая запись для оценки +лучшего случая или для ограничения заданой функции снизу. Это позволяет сделать +_**асимптотическую оценку нижней границы**_ скорости роста времени выполнения +алгоритма. + +`f(n)` принадлежит Ω(g(n)), если существуют действительные константы +с (с > 0) и 0 (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 g(n) выполняется если _**существует**_ +константа c > 0, но если f(n) = o(g(n)), тогда условие f(n) < c g(n) выполняется +для _**всех**_ констант с > 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) +выполняется для _**всех**_ констант с > 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](https://www.ozon.ru/context/detail/id/18319699/) +* [Алгоритмы. Построение и анализ](https://www.ozon.ru/context/detail/id/33769775/) + +## Ссылки + +* [Оценки времени исполнения. Cимвол O()](http://algolist.manual.ru/misc/o_n.php) +* [Асимптотический анализ и теория вероятностей](https://www.lektorium.tv/course/22903) + +## Ссылки (Eng) + +* [Algorithms, Part I](https://www.coursera.org/learn/algorithms-part1) +* [Cheatsheet 1](http://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf) +* [Cheatsheet 2](http://bigocheatsheet.com/) + -- cgit v1.2.3 From ae6f3fbb8e053d59d07026041727b2fa2969e062 Mon Sep 17 00:00:00 2001 From: Andre Polykanine Date: Sun, 23 Dec 2018 00:51:28 +0200 Subject: [asymptotic-notation/ru] Proofreading --- ru-ru/asymptotic-notation-ru.html.markdown | 450 ++++++++++++++--------------- 1 file changed, 225 insertions(+), 225 deletions(-) (limited to 'ru-ru/asymptotic-notation-ru.html.markdown') diff --git a/ru-ru/asymptotic-notation-ru.html.markdown b/ru-ru/asymptotic-notation-ru.html.markdown index 73ad80ba..7fd02c47 100644 --- a/ru-ru/asymptotic-notation-ru.html.markdown +++ b/ru-ru/asymptotic-notation-ru.html.markdown @@ -1,225 +1,225 @@ ---- -category: Algorithms & Data Structures -name: Asymptotic Notation -contributors: - - ["Jake Prather", "http://github.com/JakeHP"] - - ["Divay Prakash", "http://github.com/divayprakash"] -translators: - - ["pru-mike", "http://gihub.com/pru-mike"] -lang: ru-ru ---- - -# О-cимволика - -## Что это такое? - -О-cимволика или асимптотическая запись это система символов позволяющая оценить -время выполнения алгоритма, устанавливая зависимость времени выполнения от -увеличения объема входных данных, так же известна как оценка -сложности алгоритмов. Быстро-ли алгоритм станет невероятно медленным, когда -объем входных данных увеличится? Будет-ли алгоритм выполняться достаточно быстро, -если объем входных данных возрастет? О-символика позволяет ответить на эти -вопросы. - -## Можно-ли по-другому найти ответы на эти вопросы? - -Один способ это подсчитать число элементарных операций в зависимости от -различных объемов входных данных. Хотя это и приемлемое решение, тот объем -работы которого оно потребует, даже для простых алгоритмов, делает его -использование неоправданным. - -Другой способ это измерить какое время алгоритм потребует для завершения на -различных объемах входных данных. В тоже время, точность и относительность -(полученное время будет относиться только к той машине на которой оно -вычислено) этого метода зависит от среды выполнения: компьютерного аппаратного -обеспечения, мощности процессора и т.д. - -## Виды О-символики - -В первом разделе этого документа мы определили, что О-символика -позволяет оценивать алгоритмы в зависимости от изменения размера входных -данных. Представим что алгоритм это функция f, n размер входных данных и -f(n) время выполнения. Тогда для данного алгоритма f c размером входных -данных 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)), если -существуют действительные константы с (с > 0) и n0, такие -что `f(n)` <= `c g(n)` выполняется для всех n начиная с некоторого n0 (n > n0). - -*Пример 1* - -``` -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 * log n -``` - -Существуют-ли константы c, n0 такие что выражение верно для всех n > n0 - -``` -3log n + 100 <= 150 * log n, n > 2 (неопределенно для n = 1) -``` - -Да! По определению О-Большого `f(n)` является O(g(n)). - -*Пример 2* - -``` -f(n) = 3 * n^2 -g(n) = n -``` - -Является-ли `f(n)` O(g(n))? -Является-ли `3 * n^2` O(n)? -Посмотрим на определение О-Большого: - -``` -3 * n^2 <= c * n -``` - -Существуют-ли константы c, n0 такие что выражение верно для всех n > n0? -Нет, не существуют. `f(n)` НЕ ЯВЛЯЕТСЯ O(g(n)). - -### Омега-Большое -Омега-Большое, записывается как **Ω**, это асимптотическая запись для оценки -лучшего случая или для ограничения заданой функции снизу. Это позволяет сделать -_**асимптотическую оценку нижней границы**_ скорости роста времени выполнения -алгоритма. - -`f(n)` принадлежит Ω(g(n)), если существуют действительные константы -с (с > 0) и 0 (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 g(n) выполняется если _**существует**_ -константа c > 0, но если f(n) = o(g(n)), тогда условие f(n) < c g(n) выполняется -для _**всех**_ констант с > 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) -выполняется для _**всех**_ констант с > 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](https://www.ozon.ru/context/detail/id/18319699/) -* [Алгоритмы. Построение и анализ](https://www.ozon.ru/context/detail/id/33769775/) - -## Ссылки - -* [Оценки времени исполнения. Cимвол O()](http://algolist.manual.ru/misc/o_n.php) -* [Асимптотический анализ и теория вероятностей](https://www.lektorium.tv/course/22903) - -## Ссылки (Eng) - -* [Algorithms, Part I](https://www.coursera.org/learn/algorithms-part1) -* [Cheatsheet 1](http://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf) -* [Cheatsheet 2](http://bigocheatsheet.com/) - +--- +category: Algorithms & Data Structures +name: Asymptotic Notation +contributors: + - ["Jake Prather", "http://github.com/JakeHP"] + - ["Divay Prakash", "http://github.com/divayprakash"] +translators: + - ["pru-mike", "http://github.com/pru-mike"] +lang: ru-ru +--- + +# О-символика + +## Что это такое? + +О-символика, или асимптотическая запись, — это система символов, позволяющая +оценить время выполнения алгоритма, устанавливая зависимость времени выполнения +от увеличения объёма входных данных. Она также известна как оценка +сложности алгоритмов. Станет ли алгоритм невероятно медленным, когда +объём входных данных увеличится? Будет ли алгоритм выполняться достаточно быстро, +если объём входных данных возрастёт? О-символика позволяет ответить на эти +вопросы. + +## Можно ли по-другому найти ответы на эти вопросы? + +Один способ — это подсчитать число элементарных операций в зависимости от +различных объёмов входных данных. Хотя это и приемлемое решение, тот объём +работы, которого оно потребует, даже для простых алгоритмов делает его +использование неоправданным. + +Другой способ — это измерить, какое время алгоритм потребует для завершения на +различных объёмах входных данных. В то же время, точность и относительность +этого метода (полученное время будет относиться только к той машине, на которой +оно вычислено) зависит от среды выполнения: компьютерного аппаратного +обеспечения, мощности процессора и т.д. + +## Виды О-символики + +В первом разделе этого документа мы определили, что О-символика +позволяет оценивать алгоритмы в зависимости от изменения размера входных +данных. Представим, что алгоритм — это функция 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) и n0, такие, +что `f(n)` <= `c g(n)` выполняется для всех n, начиная с некоторого n0 (n > n0). + +*Пример 1* + +``` +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 * log n +``` + +Существуют ли константы c и n0, такие, что выражение верно для всех n > n0? + +``` +3log n + 100 <= 150 * log n, n > 2 (не определенно для n = 1) +``` + +Да! По определению О Большого `f(n)` является O(g(n)). + +*Пример 2* + +``` +f(n) = 3 * n^2 +g(n) = n +``` + +Является ли `f(n)` O(g(n))? +Является ли `3 * n^2` O(n)? +Посмотрим на определение О Большого: + +``` +3 * n^2 <= c * n +``` + +Существуют ли константы 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 g(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](https://www.ozon.ru/context/detail/id/18319699/) +* [Алгоритмы. Построение и анализ](https://www.ozon.ru/context/detail/id/33769775/) + +## Ссылки + +* [Оценки времени исполнения. Символ O()](http://algolist.manual.ru/misc/o_n.php) +* [Асимптотический анализ и теория вероятностей](https://www.lektorium.tv/course/22903) + +## Ссылки (англ.) + +* [Algorithms, Part I](https://www.coursera.org/learn/algorithms-part1) +* [Cheatsheet 1](http://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf) +* [Cheatsheet 2](http://bigocheatsheet.com/) + -- cgit v1.2.3