Существуют ли варианты регулярного времени исполнения Big-O-Notation?

9

Есть несколько примечаний, таких как или и так далее. Мне было интересно, есть ли варианты таких в реальности, как или , или они математически неверны.OO(n)O(n2)O(2n2)O(logn2)

Или было бы правильно сказать, что можно улучшить до ? Я не могу и не должен выяснять время выполнения, и мне не нужно ничего улучшать, но мне нужно знать, как вы описываете свои функции в реальности.O(5n2)O(3n2)

bv_Martn
источник
1
Во время асимптотического анализа нет существенного различия между O (5n ^ 2) и O (3n ^ 2). Они оба O (n ^ 2) и отличаются только константой. Фактически, в доказательстве вы можете даже уменьшить O (5n ^ 2) до O (3n ^ 2) или O (n ^ 2), чтобы сделать математику чище, поскольку они эквивалентны. При написании доказательства вы делаете на боковой панели заметку, что они эквивалентны. Фактически, вы можете даже поменять местами O (log n) с O (n) и заметить, что O (log n) <= O (n) на боковой панели. Заметка на боковой панели говорит читателю, что это намеренно, а не опечатка. (По крайней мере, так я поступил, когда проходил анализ алгоритмов в колледже).
jww
2
Если вы используете нотацию чтобы избавиться от мелких факторов, вы всегда можете написать что-то вроде "... улучшает время выполнения с до "и т. д. Или, что эквивалентно, и . Некоторые авторы предпочитают просто писать 5 n 2 как сокращение для первого. См., Например, учебник Трефетена и Бау. 5 n 2 + o ( n 2 ) 3 n 2 + o ( n 2 ) ( 5 + o ( 1 ) ) n 2 ( 3 + o ( 1 ) ) n 2O()5n2+o(n2)3n2+o(n2)(5+o(1))n2(3+o(1))n25n2
Йонатан N

Ответы:

21

Мне было интересно, есть ли варианты в реальности, такие как O(2n2) или O(log(n2)) , или они математически неверны.

Да, O(2n2) или O(log(n2)) являются допустимыми вариантами.

Тем не менее, вы увидите их редко, если увидите их вообще, особенно в конечных результатах. Причина в том, что O(2n2) есть O(n2) . Аналогично, O(log(n2)) есть O(logn) . Это может быть удивительно для начинающих. Тем не менее, эти равенства более или менее являются той самой причиной, по которой были введены большие O нотации, чтобы скрыть мультипликативный постоянный фактор, который часто трудно определить и относительно незначительный.

Было бы правильно сказать, что можно улучшить O(5n2) до O(3n2) ?

Это вовсе не улучшение, если временная сложность алгоритма изменяется с O(5n2) на O(3n2) или с Ω(5n2) на Ω(3n2) , потому что O(5n2) равно O(3n2) а Ω(5n2) равно Ω(3n2) . Поэтому неверно говорить, что сложность по времени улучшена сO(5n2) доO(3n2) . Правильно сказать, что временная сложность алгоритма, конечно,увеличена с5n2 до3n2 .


Упражнение 1. Покажите, что O(5n2)=O(3n2)=O(n2) .

Упражнение 2. Покажите, что O(logn)=O(log(n2)) .

Упражнение 3. Покажите, что Ω(n2+n)=Ω(n2) .

Джон Л.
источник
1
@bv_Martn Вот хорошая ссылка, чтобы понять, как определяется обозначение (просто простое исчисление пределов!): math.stackexchange.com/questions/925053/…O(n)
Махаджан,
2
Единственный раз, когда я видел постоянные факторы в нотации big-O, это когда кто-то хочет подчеркнуть, что хотя два алгоритма относятся к одному классу сложности, один из них строго быстрее другого.
Марк
7
@AkshatMahajan Единственный ответ на этот вопрос /math/925053 явно неправильный. Есть много надежных источников на больших обозначениях. O
Джон Л.
1
«Правильно сказать, что временная сложность алгоритма улучшена с 5n ^ 2 до 3n ^ 2», хотя точное время выполнения часто варьируется для разных входных размеров и значений. Кроме того, это включает взвешивание всех операций / фокусирование на одной операции, что может мало сказать о постоянных факторах, которые вы получите в реальном мире, или быть сопоставимым с другими алгоритмами, использующими разные веса. Таким образом, хотя он может иметь несколько допустимых вариантов использования, произнесение чего-то подобного выше имеет ограниченную полезность (вероятно, поэтому его редко можно увидеть).
Dukeling
1
@Mark: это просто неправильно.
user21820
13

Вы всегда можете не использовать эту запись вообще. То есть вы можете определить функцию f(n) как можно точнее, а затем попытаться улучшить ее. Например, у вас может быть алгоритм сортировки, который делает f(n) сравнения, поэтому вы можете попытаться придумать другой алгоритм сортировки, который выполняет только g(n) сравнения. Конечно, все виды функций f(n) существуют (в теории) и также могут появиться (на практике).

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

Юхо
источник
Ну, мне это пока не нужно на практике. Или в теории, на самом деле, мне просто нужно знать, существуют ли в википедии определения O (1) -O (n!) Единственные, которые существуют, или если в действительности вы могли бы описать их по-разному, если они разные, такие как O (7н). Я боюсь, что если я воспользуюсь этим, профессор математики потеряет свои крылья
bv_Martn
1
Любое определение, которое кто-либо делает, существует. Вы должны очень внимательно прочитать, что означают обозначения или O ( n ! ), Потому что ваш вопрос не имеет смысла. Там нет ярлыков. Если вы хотите понять, что значит математический контент, вы должны быть готовы потратить некоторое время. O(1)O(n!)
Juho
6
@bv_Martn Профессор математики с большей вероятностью перевернется, потому что вы просматриваете список примеров в виде списка определений. Большая часть математики заключается в том, чтобы определять вещи так, чтобы они работали в целом, а не только в конкретных случаях. Ваш вопрос в основном является более продвинутой версией "Википедия говорит, что я могу добавить один, добавить два и добавить семнадцать. Но могу ли я добавить и другие числа?"
Дэвид Ричерби
7

Хотя принятый ответ довольно хороший, он все равно не затрагивает реальную причину, по которой O(n)=O(2n) .

Нотация Big-O описывает масштабируемость

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

Возьмите бинарный поиск, например. Учитывая отсортированный список, как вы можете найти произвольное значение внутри него? Ну, вы могли бы начать с середины. Поскольку список отсортирован, среднее значение скажет вам, в какой половине списка находится ваше целевое значение. Таким образом, список, который вы должны искать, теперь разделен пополам. Это можно применить рекурсивно, затем перейти к середине нового списка и так далее, пока размер списка не станет равным 1, и вы не найдете свое значение (или оно не существует в списке). Удвоение размера списка добавляет к алгоритму только один дополнительный шаг - логарифмическое соотношение. Таким образом, этот алгоритм O(logn), Логарифм - это основание 2, но это не имеет значения - суть отношения заключается в том, что умножение списка на постоянное значение только добавляет постоянное значение времени.

Сравните стандартный поиск по несортированному списку - в этом случае единственный способ найти значение - проверить каждый. В худшем случае (что конкретно подразумевает Big-O), ваше значение находится в самом конце, что означает, что для списка размера n вы должны проверить n значений. Удвоение размера списка удваивает количество проверок, что является линейной зависимостью. O(n) . Но даже если вам нужно было выполнить две операции с каждым значением, например, при некоторой обработке линейные отношения сохраняются. O(2n) просто бесполезен в качестве дескриптора, так как он описывает ту же масштабируемость, что и O(n) .

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

разброс
источник
5
Самая большая проблема с этим типом ответа состоит в том, что он не затрагивает определение Большого О, а просто использует его в качестве некой интуитивной магии, как в «Посмотрите, когда вы делаете это и это, это ». Лично я думаю, что гораздо более поучительно сказать кому-то, что Big Oh не имеет абсолютно никакого отношения к алгоритмам, и начать с этого. O(n)
Юхо
3
@Juho Поучительно, может быть, но в конечном счете бесполезно для подавляющего большинства компьютерных ученых.
разброс
4
С этим я должен не согласиться. Обозначение себя как ученого-компьютерщика не должно быть оправданием для того, чтобы не понимать, что означает обозначение, которое вы используете, то есть пропускать всю математику.
Juho
3
Да. Я не возражаю против того, что программисты не понимают этого, но если вы хотите назвать себя ученым , то это основной материал.
Дэвид Ричерби
2
@dkaeae Нет, я имею в виду людей, которые работают в этой сфере, например, разработчиков программного обеспечения.
разброс
5

O(f)fg(n)=O(f(n))cg(n)cf(n)nf

g(n)=O(f(n))g(n)=O(2f(n))g(n)cf(n)ng(n)c22f(n)g(n)=O(2f(n))с/2

logn2log(n2)2журналN

O

Дэвид Ричерби
источник
4

Посмотрите на определение O (f (n)), и вы увидите, что, например, O (2n ^ 2) и O (n ^ 2) абсолютно одинаковы. Изменение алгоритма с 5n ^ 2 на 3n ^ 2 операций - это улучшение на 40 процентов. Переход от O (5n ^ 2) к O (3n ^ 2) на самом деле не является каким-либо изменением, они одинаковы.

Снова прочтите определение O (f (n)).

gnasher729
источник
4

O(f(n))={g(n)|n,c>0:m>n:c×g(m)f(m)}

=

O(n)=O(2n)

чокнутый урод
источник
4
log(n!)=nlognn+O(logn) encourages us to view O(f) as both "the set of functions such that [...]" and "some function such that [...]"
David Richerby