#algorithm
#алгоритм
Вопрос:
Мы используем omega() для наилучшего времени выполнения и O() в качестве наихудшего времени выполнения. Но в приведенном ниже тексте из CLRS они используют omega() для наихудшего времени выполнения (подчеркнутая часть). Можно ли использовать omega() в качестве наихудшего времени выполнения вместо O()?
Ответ №1:
-
«Алгоритм выполняется за O(f(n))» означает, что существует константа k, такая, что алгоритм выполняется не более чем за kf(n).
-
«Алгоритм выполняется в Omega(f(n))» означает, что существует константа k, такая, что алгоритм выполняется по крайней мере за kf(n).
-
Когда вы говорите «даже в худшем случае алгоритм выполняется в O (f (n))», вы дополняете свой алгоритм: вы говорите, что алгоритм гарантированно не будет медленнее, чем kf (n).
-
Когда вы говорите «наихудший случай выполняется в Omega (f (n))», вы критикуете свой алгоритм: вы говорите, что для каждого n существует вход размером n, на котором алгоритм будет медленнее, чем kf (n).
В большинстве ситуаций люди заинтересованы в инструкции O() и не слишком беспокоятся о инструкции Omega().
Пример: время выполнения быстрой сортировки
-
Быстрая сортировка выполняется за O(n ^ 2)
-
Для каждого n существует определенный массив размера n, для которого выполняется быстрая сортировка в Omega(n ^2)
-
Однако неправильно говорить, что время выполнения быстрой сортировки равно Omega(n ^ 2), поскольку в некоторых случаях (фактически, в большинстве случаев) быстрая сортировка выполняется намного меньше, чем n ^ 2
-
Если массив равномерно перетасовывается случайным образом, то ожидаемое время выполнения быстрой сортировки равно O (n log n)
-
Обычно мы говорим что-то вроде «Время выполнения быстрой сортировки равно O (n ^ 2), а его среднее время выполнения равно O (n log n)».
Комментарии:
1. Большое спасибо, Стеф! Так неправильно ли говорить, что время выполнения быстрой сортировки равно Omega (n ^ 2)?
2. Да, неправильно говорить, что время выполнения быстрой сортировки равно Omega(n ^ 2). Наихудшее время выполнения быстрой сортировки равно Omega(n^2). Но в лучшем случае время выполнения быстрой сортировки равно O(n log n) (а также Omega(n log n)).
3. Обычно мы говорим что-то вроде «Время выполнения быстрой сортировки равно O (n ^ 2), а его среднее время выполнения равно O (n log n)». «Среднее время выполнения» здесь очень неоднозначно, но означает «ожидаемое время выполнения, если массив был равномерно перетасован случайным образом». Однако написать строгое доказательство среднего времени выполнения сложнее, чем кажется.
4. Извините, Стеф, могу я спросить, почему это неправильно, пожалуйста?
5. Потому что в некоторых случаях (фактически, в большинстве случаев) быстрая сортировка выполняется намного быстрее, чем n ^ 2. Таким образом, вы не можете сказать «быстрая сортировка выполняется в Omega (n ^ 2)».