предисловие
Эта статья включена в альбом:dwz.win/HjK, нажмите, чтобы получить дополнительные знания о структурах данных и алгоритмах.
Привет, я брат Тонг, хардкорный человек, который каждый день взбирается на двадцать шесть этажей и не забывает читать исходный код.
В предыдущих разделах мы узнали, как анализировать сложность алгоритма вместе, и проанализировали сложность алгоритма для наихудшего, среднего, наилучшего и наихудшего сценариев без тупиков.Когда мы выражаем сложность, обычно большая- O используется для его представления.
Однако в других книгах вы, возможно, встречали такие символы, как Θ, Ω, o, ω и т. д.
Так что же означают эти символы?
В этом разделе мы решим эту проблему.
произношение
Давайте сначала исправим волну произношения:
- О, / əʊ /, большой О
- о, / əʊ /, маленький о
- Θ, /ˈθiːtə/, тета
- Ω, /oʊˈmeɡə/, большая омега
- ω, /oʊˈmeɡə/, маленькая омега
Разве это не отличается от того, чему учил учитель ^^
Математическое объяснение
Θ
Θ определяет точную асимптотику, как бы это сказать?
Выразите это в виде функции:
对于f(n)，存在正数n0、c1、c2，使得当 n>=n0 时，始终存在 0 <= c1*g(n) <= f(n) <= c2*g(n)，则我们可以用 f(n)=Θ(g(n))表示。
Графически представить:
Θ определяет как верхнюю, так и нижнюю границу, а f(n) лежит между верхней и нижней границами и включает знак равенства.
Например, f (n) = 2n ^ 2 + 3n + 1 = Θ (n ^ 2), в настоящее время g (n) получается путем удаления младших членов и постоянных членов с f (n), потому что есть должно быть некоторое положительное число n0, c1, c2, такое что 0
Что ж, если вы можете понять Θ, следующие четыре понять несложно.
O
O определяет верхнюю границу алгоритма.
Выразите это в виде функции:
对于f(n)，存在正数n0、c，使得当 n>=n0 时，始终存在 0 <= f(n) <= c*g(n)，则我们可以用 f(n)=O(g(n))表示。
Графически представить:
O определяет только верхнюю границу, пока f (n) не больше, чем c * g (n), можно сказать, что f (n) = O (g (n)).
Например, для сортировки вставками мы говорим, что ее временная сложность равна O(n^2), но если она выражается в Θ, ее нужно разделить на две части:
- В худшем случае его временная сложность равна Θ(n^2);
- В лучшем случае его временная сложность равна Θ(n).
n ^ 2 здесь — это просто наименьшая верхняя граница в наборе функций от g (n).Конечно, g (n) также может быть равно n ^ 3.
Однако обычно мы говорим, что сложность относится к наименьшей верхней границе.Например, если временная сложность сортировки вставками здесь O(n^3), теоретически это нормально, но не соответствует соглашению.
Лучший случай для сортировки вставками — это когда отсортирован сам массив.
o
o также определяет верхнюю границу алгоритма, но не содержит параллелей, что является неточной верхней границей или свободной верхней границей (переведенной в некоторых книгах как некомпактная верхняя граница).
Выразите это в виде функции:
对于f(n)，存在正数n0、c，使得当 n>n0 时，始终存在 0 <= f(n) < c*g(n)，则我们可以用 f(n)=o(g(n))表示。
Графически представить:
o означает, что это только случай большого O минус равные, а остальное поведение точно такое же, как у большого O.
Ω
Ω определяет нижнюю границу алгоритма, которая является полной противоположностью O.
Выразите это в виде функции:
对于f(n)，存在正数n0、c，使得当 n>=n0 时，始终存在 0 <= c*g(n) <= f(n)，则我们可以用 f(n)=Ω(g(n))表示。
Графически представить:
Ω определяет только нижнюю границу, если f(n) не меньше, чем c*g(n), можно сказать, что f(n)=Ω(g(n)).
Например, для сортировки вставками можно сказать, что ее временная сложность равна Ω(n), однако обычно это не имеет смысла, поскольку сортировка вставками редко бывает в лучшем случае, в основном в худшем или среднем случае.
ю
ω также определяет нижнюю границу, за исключением того, что она не содержит равных.Это неточная нижняя граница, или граница Панасоника (в некоторых книгах переводится как некомпактная нижняя граница).
Выразите это в виде функции:
对于f(n)，存在正数n0、c，使得当 n>n0 时，始终存在 0 <= c*g(n) < f(n)，则我们可以用 f(n)=ω(g(n))表示。
Графически представить:
ω означает, что это только тот случай, когда большое Ω удалено и равно, а другие поведения точно такие же, как у большого Ω.
народное понимание
| символ | значение | народное понимание |
|---|---|---|
| Θ | точная асимптотика | Эквивалентно "=" |
| O | Верхняя граница | Эквивалентно " |
| o | Сун Шанцзе | Эквивалентно " |
| Ω | Нижний мир | Эквивалентно ">=" |
| ю | Панасоник | Эквивалентно ">" |
резюме
Чтобы помочь учащимся быстро получить доступ к материалам на английском языке, Тонг Гэ обобщил английские слова, используемые в этих разделах:
| китайский язык | английский |
|---|---|
| сложность | complexity |
| временная сложность | time complexity |
| космическая сложность | space complexity |
| Асимптотический анализ | asymptotic analysis |
| худший случай | the worst case |
| лучший случай | the best case |
| Средняя ситуация | the average case |
| точная асимптотика | exact asymptotic behavior |
| условия более низкого порядка | low order terms |
| Постоянный срок (предпостоянный) | leading constants |
| Сун Шанцзе | loose upper-bound |
постскриптум
В этом разделе мы объясняем значения Θ, O, o, Ω и ω с трех аспектов: произношения, математики и народного понимания, и, наконец, даем английский язык, соответствующий терминам, используемым в этих разделах. Вы также можете быстро ознакомиться с этой информацией.
Однако в процессе общения с людьми мы все же привыкли использовать нотацию большой О. Во-первых, она представляет наихудший случай, а наихудший случай обычно может напрямую отражать сложность алгоритма.Во-вторых, так проще писать .
Поэтому нам нужно запомнить только большую букву О, но когда другие упоминают Θ, Ω и ω, мы знаем, что они означают.
Так много было сказано в предыдущих разделах, но на самом деле речь идет только об очень простой алгоритмической сложности.
Итак, каковы общие сложности алгоритма?
В следующем разделе поговорим.
Подпишитесь на «Tong Ge Read Source Code» владельца официальной учетной записи, чтобы разблокировать больше исходного кода, основ и знаний об архитектуре.