Большой-ой против большой тета

Ответ 1

Big-O - верхняя граница.

Big-Theta является плотной границей, т.е. верхней и нижней границей.

Когда люди только беспокоятся о том, что может быть самым худшим, big-O достаточно; то есть он говорит, что "это не может стать намного хуже, чем это". Чем жестче граница, тем лучше, конечно, но сложную связь не всегда легко вычислить.

См. также

• Википедия/примечание Big O

Связанные вопросы

• В чем разница между Θ (n) и O (n)?

Следующая цитата из Википедии также проливает некоторый свет:

Неформально, особенно в области информатики, нотация Big O часто разрешено несколько злоупотреблять, чтобы описать асимптотическую жесткую границу где использование обозначения Big Theta может быть более целесообразным в данный контекст.

Например, при рассмотрении функции T(n) = 73n ³+ 22n ²+ 58 все это, как правило, приемлемо, но плотность связанного (т.е., пули 2 и 3 ниже), как правило, сильно предпочтительны по отношению к слабости связанного (т.е. пуля 1 ниже).

• T(n) = O(n ¹⁰⁰), который идентичен T(n) ∈ O(n ¹⁰⁰)
• T(n) = O(n ³), который идентичен T(n) ∈ O(n ³)
• T(n) = Θ(n ³), который идентичен T(n) ∈ Θ(n ³)

Соответствующие английские утверждения:

• T(n) растет асимптотически не быстрее, чем n ¹⁰⁰
• T(n) растет асимптотически не быстрее, чем n ³
• T(n) растет асимптотически так же быстро, как n ³.

Таким образом, хотя все три утверждения верны, в дальнейшем все больше информации содержится в каждый. Однако в некоторых полях, нотация Big O (пули номер 2 в списках выше) будет использоваться чаще, чем обозначение Big Theta (пули № 3 в списки выше), потому что функции, которые растут медленнее, более желательны.

Ответ 2

Я математик, и я снова и снова видел и нуждался в нотах большой О, большой-тета и большой Омеги, а не только для сложности алгоритмов. Как говорили люди, большая тэта - двусторонняя связь. Строго говоря, вы должны использовать его, когда хотите объяснить, насколько это может сделать алгоритм, и что либо этот алгоритм не может сделать лучше, либо что ни один алгоритм не сможет сделать лучше. Например, если вы говорите: "Сортировка требует Θ (n (log n)) сравнений для ввода наихудшего случая", то вы объясняете, что существует алгоритм сортировки, который использует сравнения O (n (log n)) для любого ввода; и что для каждого алгоритма сортировки есть вход, который заставляет его делать сравнения Ω (n (log n)).

Теперь одна узкая причина, по которой люди используют O вместо Ω, - это отказаться от отказов от худших или средних случаев. Если вы говорите: "Сортировка требует O (n (log n)) сравнений", то инструкция по-прежнему сохраняется для благоприятного ввода. Другая узкая причина заключается в том, что даже если один алгоритм для выполнения X принимает время Θ (f (n)), другой алгоритм может сделать лучше, поэтому вы можете только сказать, что сложность самого X - это O (f (n)).

Однако существует более широкая причина, по которой люди неофициально используют O. На человеческом уровне боль всегда делает двусторонние высказывания, когда обратная сторона "очевидна" из контекста. Поскольку я математик, я бы в идеале всегда был осторожен, чтобы сказать: "Я возьму зонтик, если и только если идет дождь", или "Я могу жонглировать 4 мячами, но не 5", вместо "Я возьму зонтик, если он дождей" или "я могу жонглировать 4 мячами". Но другие половинки таких заявлений часто явно предназначены или явно не предназначены. Это просто человеческая природа, чтобы быть неаккуратной относительно очевидного. Это смущает расщепление волос.

К сожалению, в строгой области, такой как математика или теория алгоритмов, она также путается не разделить волосы. Люди неизбежно скажут O, когда они должны были сказать Ω или Θ. Пропуск деталей, потому что они "очевидны", всегда приводит к недоразумениям. Для этого нет решения.

Ответ 3

Потому что у моей клавиатуры есть клавиша O.
Он не имеет ключа Θ или Ω.

Я подозреваю, что большинство людей одинаково ленивы и используют O, когда они имеют в виду Θ, потому что их легче печатать.

Ответ 4

Одна из причин, по которой большой O используется так сильно, - это потому, что он так много используется. Многие люди видят обозначение и думают, что знают, что это значит, а затем используют его (ошибочно) сами. Это очень часто случается с программистами, чье официальное образование только зашло до сих пор - я был когда-то виноват сам.

Другим является то, что легче набирать большой O на большинстве негреческих клавиатур, чем большая тета.

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

Хотя, конечно, многие алгоритмы имеют наихудший случай в очень распространенных обстоятельствах - классический пример - вставка в порядке в двоичное дерево, чтобы получить то, что эффективно является односвязным списком. "Реальная" оценка средней производительности должна учитывать относительную частоту различных видов ввода.

Ответ 5

Бонус: почему люди, по-видимому, всегда используют big-oh, когда разговаривают неформально?

Потому что в big-oh этот цикл:

for i = 1 to n do
    something in O(1) that doesn't change n and i and isn't a jump

есть O(n), O(n^2), O(n^3), O(n^1423424). big-oh - это только верхняя граница, что упрощает вычисление, потому что вам не нужно искать жесткую привязку.

Вышеуказанный цикл только big-theta(n).

Какова сложность решета эратосфенов? Если бы вы сказали O(n log n), вы бы не ошиблись, но это был бы не лучший ответ. Если вы сказали big-theta(n log n), вы ошибаетесь.

Ответ 6

Потому что есть алгоритмы, чей наилучший вариант быстр, и, следовательно, он технически большой O, а не большой Theta.

Big O - верхняя граница, большая Theta - отношение эквивалентности.

Ответ 7

Здесь есть много хороших ответов, но я заметил, что чего-то не хватает. Большинство ответов, похоже, подразумевают, что причина, по которой люди используют Big O over Big Theta, представляет собой проблему с трудностями, и в некоторых случаях это может быть правдой. Часто доказательство, приводящее к результату Big Theta, гораздо более активно, чем результат, который приводит к Big O. Это обычно справедливо, но я не верю, что это имеет большое отношение к использованию одного анализа над другим.

Говоря о сложности, мы можем сказать много вещей. Большая сложность времени O просто говорит нам, что алгоритм гарантирован для запуска внутри, верхней границы. Большая Омега гораздо реже обсуждается и рассказывает нам о минимальном времени, которое гарантирован алгоритм для запуска, нижней границе. Теперь Большая Тета говорит нам, что оба эти числа на самом деле одинаковы для данного анализа. Это говорит о том, что приложение имеет очень строгое время выполнения, которое может отклоняться только на величину, асимптотически меньшую нашей сложности. Многие алгоритмы просто не имеют верхней и нижней границ, которые оказываются асимптотически эквивалентными.

Что касается вашего вопроса, использующего Big O вместо Big Theta, технически всегда будет действительным, а использование Big Theta вместо Big O будет справедливым только тогда, когда Big O и Big Omega оказались равными. Например, сортировка вставки имеет временную сложность Big О при n ^ 2, но ее наилучший сценарий ставит свою большую Омегу в n. В этом случае было бы неверно говорить о том, что его временная сложность - это Большая тета n или n ^ 2, поскольку они являются двумя различными границами и должны рассматриваться как таковые.

Ответ 8

Я видел Большую Тету, и я уверен, что меня учили разнице в школе. Я должен был все выяснить. Вот что говорит Википедия:

Big O - наиболее часто используемая асимптотическая нотация для сравнения функций, хотя во многих случаях Big O может быть заменена Big Theta Θ для асимптотически более жестких границ.

Источник: Big O Notation # Связанная асимптотическая нотация

Я не знаю, почему люди используют Big-O, когда говорят формально. Может быть, потому, что большинство людей больше знакомы с Big-O, чем с Big-Theta? Я забыл, что Биг-Тета даже существовала, пока ты не напомнил мне. Хотя теперь, когда моя память обновлена, я могу использовать ее в разговоре.:)