Почему Большой О преподается вместо Большой Тэты?

21

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

например, «Быстрая сортировка - это O (N ^ 2)» может превратиться в гораздо более сильное утверждение «Быстрая сортировка - это Θ (N ^ 2)»

Хотя использование Big O технически правильно, разве более распространенное использование Big Theta не будет более выразительным и приведет к меньшему беспорядку? Есть ли какая-то историческая причина, почему этот Большой О чаще используется?

Википедия отмечает:

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

notation big-o big-theta tskuzzy
источник
3
Я знаю, что это на самом деле не относится к вопросу, но быстрая сортировка не тета (N ^ 2). Это O (N ^ 2).
Йстернберг
Big O - это то, что нужно знать новичкам / не-CS. Большая тэта - это то, что описано во введении в алгоритмы, которое не будет восприниматься каждым майором. Те, у кого был класс алгоритмов, могут читать в нотацию Big O глубже, если захотят. Я не уверен, к чему относится цитата из Википедии. С академическими публикациями вы получите перерезанное горло на конференции, если вы перепутаете Big O и Big Theta. Некоторые люди проводят всю свою жизнь в погоне за тэтой, и это тяжелые проблемы.
Работа
@jsternberg Технически вы правы. Это также верно, но бессмысленно: «Быстрая сортировка в любом случае (худшая, лучшая,…) равна O (n ^ 100). Но я согласен с OP, это должно быть более точно: наихудший случай быстрой сортировки - Theta (N ^ 2), QuickSort в лучшем случае - тэта (NlogN). Потому что в каждом случае мы получим разные функции
Эльдар

Ответы:

26

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

Когда он работает быстрее, чем ожидалось для данного ввода - это нормально, это не критическая точка. Это в основном незначительная информация.

Некоторые алгоритмы, как заметил @Peter Taylor, вообще не имеют жесткой границы. См., Например, быструю сортировку O (n ^ 2) и Omega (n).

Кроме того, жесткие границы часто сложнее вычислить.

Смотрите также:

сокол
источник
6
Но Big O не обязательно соответствует производительности в худшем случае. Я мог бы сказать, что быстрая сортировка выполняется в O (2 ^ n) и будет на 100% правильной. Было бы гораздо более значимым, если бы я сказал, что алгоритм X работает в тэте (N ^ 2), а не в O (N ^ 2).
tskuzzy
Кроме того, при анализе алгоритмов почти всегда вычисляются жесткие границы, а не просто верхняя граница. Я спрашиваю, почему люди не могут использовать гораздо более выразительные тэта-записи, когда они могут.
tskuzzy
9
Я сказал вам, почему большинство программистов не используют его. Мы ленивы и не нуждаемся в такой точности. Никто не мешает вам использовать большую тэту, если хотите. Давай, сделай это. Ваш выбор алгоритма, скорее всего, не принесет такой большой пользы. Я никогда не слышал о программисте, сбитом с толку большой буквой О. Я тоже не нахожу это в замешательстве.
Сокол
9

Одна из причин заключается в том, что во многих случаях known просто неизвестно. Например, Матричное умножение - это O (n ^ 2.376), но нет жесткой границы. Конечно, насколько я могу судить, это жесткая граница для матричного умножения, но мы не знаем его значение.

MSalters
источник
Но это будут границы времени выполнения проблемы, а не конкретного алгоритма. Хотя умножение матриц в целом может быть решено быстрее, чем кубическое время, наивный алгоритм равен algorithm (n ^ 3), несмотря ни на что.
tskuzzy
5
@tskuzzy, быстро сортируй. У него нет привязки к тэте, потому что это O (n ^ 2) и Omega (n).
Питер Тейлор