Большой о по сравнению с большой тетой [дубликат]

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

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

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

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

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

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

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

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

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

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

Я математик, и я видел и нуждался в обозначениях big-O, big-Theta и big-Omega снова и снова, и не только для сложности алгоритмов. Как говорили люди, big-Theta - это двустороннее ограничение. Строго говоря, ее следует использовать, когда вы хотите объяснить, что именно так хорошо может работать алгоритм, и что либо этот алгоритм не может работать лучше, либо ни один алгоритм не может работать лучше. Например, если вы говорите: "Сортировка требует Θ(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, когда им следовало бы сказать Ω или Θ. Пропуск деталей, потому что они "очевидны", всегда приводит к недопониманию. Для этого нет решения.

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

Другое дело, что на большинстве негреческих клавиатур легче набрать большую букву О, чем большую тэту.

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

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

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

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