Big-oh vs big-theta [дубликат]

Я математик, и я видел и нуждался в нотации big-O, big-Theta и big-Omega снова и снова, а не только для сложности алгоритмов. Как говорили люди, Биг-тета-это двусторонняя граница. Строго говоря, вы должны использовать его, когда хотите объяснить, что это то, как хорошо алгоритм может сделать, и что либо этот алгоритм не может сделать лучше, либо что никакой алгоритм не может сделать лучше. Например, если вы говорите "сортировка требует comparisons(n (log n)) сравнения для худшего случая ввода", то вы объясняя, что существует алгоритм сортировки, который использует o(n(log n)) сравнения для любого входа; и что для каждого алгоритма сортировки есть вход, который заставляет его делать ω(n(log n)) сравнения.

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

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

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

потому что моя клавиатура имеет клавишу o.
Он не имеет ключа Θ или Ω.

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

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

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

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

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

бонус: почему люди, казалось бы, всегда используют 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), вы были бы неправы.

потому что есть алгоритмы, чей лучший случай быстр, и поэтому технически это большой O, а не большой тета.

Big O-это верхний предел большой тета-это отношение эквивалентности.

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

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

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

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

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

источник: Big O Notation#связанные асимптотические обозначения

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