) намного сложнее рассчитать.

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

O: Big-O запись в худшем случае.
Θ: тета-обозначение среднего случая.
Ω: омега нотация в лучшем случае.

Почему Википедия представляет скорость алгоритмов только в Big-O, включая ее средний, лучший и худший случаи? Почему они не заменили эти формальные ключевые слова?

 Cine10 янв. 2011 г., 11:47
В основном люди просто заботятся об О, так как это наихудший случай, который часто имеет наибольшее значение.

Ответы на вопрос(2)

где вы нашли эти определения, но я бы посчитал их неправильными.

Наилучшие, средние и наихудшие случаи - это, как правило, функции, превышающие размер ввода.

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), Θ (н2), Ом (n2).

Теперь вы можете сказать: это не очень полезно, зачем нам три границы, если они всегда одинаковы? Почему бы нам просто не использовать Тету везде?

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

Однако для некоторых алгоритмов сложно точно определить, что такое жесткая граница, в то время как легко получить верхнюю и / или нижнюю границу. Неоптимизированный алгоритм расчетаЧисла Фибоначчи один такой пример - это не так уж сложно найтиверхняя граница O (2n) а такженижняя граница Ω (1,5n), но жесткая граница ~ θ (1.6n) намного сложнее рассчитать.

Решение Вопроса

хотя они имеют похожее значение.

Обозначение 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" в левой части другой функцией "fсредний«Это учитывает только наиболее вероятные результаты. Таким образом, для быстрой сортировки f = O (n²) - лучшее, что вы можете получить, но fсредний = O (n log n).

 Dukeling09 сент. 2017 г., 15:13
Этот ответ неверен. Наилучшие, средние и наихудшие случаи - функции, а O, Θ и Ω - границы этих функций. Вы можете представить лучший случай в терминах O, Θ или Ω. Вот почему Википедия перечисляет big-O для всех случаев, вместо того, чтобы использовать разные обозначения для каждого. Смотрите ответ, который я разместил ниже.
 gsamaras09 сент. 2017 г., 12:23
Виктор, пожалуйста, посмотрите на этовопрос.

Ваш ответ на вопрос