Определение нотации Big-O
Я действительно хочу знать настоящее определение. Я пытался прочитать книгу, но не мог ее понять.
O: Big-O запись в худшем случае.
Θ: тета-обозначение среднего случая.
Ω: омега нотация в лучшем случае.
Почему Википедия представляет скорость алгоритмов только в Big-O, включая ее средний, лучший и худший случаи? Почему они не заменили эти формальные ключевые слова?
2 ответа
O, Θ и Ω не представляют наихудший, средний и лучший случай; хотя они имеют похожее значение.
Обозначение Big-O f(n) = O(g(n)) означает, что f растет медленнее, чем g для больших значений n ("n> n0" означает "для больших значений n" в этом контексте). Это не означает, что g - наихудший случай: g может быть хуже, чем наихудший случай (например, быстрая сортировка также O (n!)). Для более сложных алгоритмов ведутся исследования с целью определения наименьшего Big-O для их реальной сложности: первоначальный автор в основном находит верхнюю границу Big-O.
Обозначение Ω означает обратное (f растет быстрее, чем g), что означает, что оно может быть лучше, чем в лучшем случае (например, все алгоритмы имеют Ω (1)).
Существует много алгоритмов, для которых не существует единственной функции g такой, что сложность равна O (g) и Ω (g). Например, сортировка вставки имеет нижнюю границу Big-O, равную O (n²) (то есть вы не можете найти ничего меньше n²) и верхнюю границу Ω (n).
Другие алгоритмы: сортировка слиянием - это O (n log n) и Ω (n log n). Когда это происходит, оно записывается как Θ (n log n), что означает, что не все алгоритмы имеют сложность Θ-нотации (и, в частности, алгоритмы с наихудшими или лучшими случаями не имеют таковых).
Чтобы избавиться от наихудших случаев, которые несут очень низкую вероятность, достаточно часто исследовать сложность среднего случая - заменяя стандартное значение "f" в левой части другой функцией "favg", которая учитывает только наиболее вероятные результаты. Таким образом, для быстрой сортировки f = O(n²) - лучшее, что вы можете получить, но favg = O (n log n).
Я не уверен, где вы нашли эти определения, но я бы посчитал их неправильными.
В лучшем, среднем и худшем случаях все функции обычно превышают размер ввода.
Big-O, Theta и Omega указывают, соответственно, верхнюю, жесткую и нижнюю границы любой заданной функции.
То есть, в лучшем случае имеет место биг-О, Тета и Омега. То же самое касается среднего и худшего случая.
Смотрите также: Как O и Ω относятся к худшему и лучшему случаям?
Примечание: big-O обычно (возможно, неправильно) используется для обозначения жесткой границы (вместо тета).
Давайте рассмотрим пример вставки сортировки.
Наилучший случай, когда он уже отсортирован, и в этом случае это займет линейное время, то есть f(n) = k1n время для некоторой константы k1,
k1n есть O (n), Θ(n), Ω(n). Согласно определениям, мы также можем сказать, что это O (n2), O (n3),... или Ω(1), Ω(log n), Ω(log log n), ..., но это как правило, ожидается, чтобы представить самый жесткий предел.
Худшие и средние случаи g(n) = k2n2 а также h(n) = k3n2, которые оба O (n2), Θ (n2), Ω (n2).
Теперь вы можете сказать: это не очень полезно, зачем нам три границы, если они всегда одинаковы? Почему бы нам просто не использовать Тету везде?
В общем, вы были бы абсолютно правы - алгоритмы часто описываются в терминах только одной из границ (обычно это жесткая граница).
Однако для некоторых алгоритмов сложно точно определить, что такое жесткая граница, в то время как легко получить верхнюю и / или нижнюю границу. Неоптимизированный алгоритм для вычисления чисел Фибоначчи является одним из таких примеров - не так уж сложно найти верхнюю границу O (2n) и нижнюю границу Ω (1,5n), но жесткая граница ~θ(1,6n) намного сложнее рассчитать.