Быстрая сортировка омега-нотации

Question

Лучшим случаем для быстрой сортировки является n log (n), но все используют нотацию Big-O, чтобы описать лучший случай как O (n log (n)).Из моего понимания обозначений, Quicksort имеет Big-Omega (n log (n)) и O (n ^ 2).Это правильно, или я неправильно понимаю обозначение Big-Omega?

Answer 1

Big-O и Big-Omega - это способы описания функций, а не алгоритмы.Говорить о быстрой сортировке O (n ^ 2) неоднозначно, потому что вы не говорите, какое свойство алгоритма вы описываете.

Алгоритмы могут иметь сложность времени в лучшем случае и сложность времени в худшем случае.Это временные сложности алгоритма, если для каждого размера ввода используются входы с наилучшими или худшими показателями.

Это отличается от Big-O и Big-Omega, которые описывают верхнюю и нижнюю границы функции.

Сложности времени даны как функция размера ввода, который может иметь свои верхние и нижние границы.

Например, если вы знали, что лучший случай не былхуже, чем nlogn, тогда можно сказать, что сложность времени в лучшем случае - O (nlogn).Если бы вы знали, что это был точно nlogn, то было бы точнее сказать Theta (nlogn).

Answer 2

У вас неверные данные.Биг-О технически считается худшим случаем.QuickSort имеет средний случай O (n log n) и худший случай O (n ^ 2).Исходя из технического определения, правильный Big-O для QuickSort равен n ^ 2.Но шансы случайного получения этой производительности практически равны нулю (если вы не запустите QuickSort в уже отсортированном списке), поэтому QuickSort присваивается значение Big-O из n log n, хотя это не является технически правильным.

Big-С другой стороны, омега технически определяется как «по крайней мере, так долго», так что это нижняя граница.Это означает, что QuickSort имеет Big-Omega (n log n) и n ^ 2 не имеет ничего общего с QuickSort и Big-Omega.