Анализ худшего случая не равен асимптотическим границам

Question

Может кто-нибудь объяснить мне, почему это правда. Я слышал, как профессор упомянул об этом его лекции.

Answer 1

Два понятия ортогональны.

У вас может быть наихудший случай асимптотики. Если f(n) обозначает наихудшее время, затраченное данным алгоритмом с вводом n, вы можете иметь, например. f(n) = O(n^3) или другие асимптотические верхние границы наихудшей временной сложности.

Аналогичным образом, вы можете иметь g(n) = O(n^2 log n), где g(n) - среднее время, затраченное на тот же алгоритм с (скажем) равномерно распределенными (случайными) входами размера n.

Или вы можете иметь h(n) = O(n) где h(n) среднее время, затрачиваемое одним и тем же алгоритм с особенно распределенными случайными входами размера n (например, почти отсортированными последовательностями для алгоритма сортировки).

Асимптотические обозначения - это «мера». Вы должны указать, что вы хотите сосчитать: наихудший случай, лучший случай, средний и т. Д.

Иногда вас интересует сообщение асимптотические нижние границы (скажем) сложность наихудшего случая.Затем вы пишете f(n) = Omega(n^2), чтобы заявить, что в худшем случае сложность не менееn^2. Обозначение с большой омегой противоположно большому-O: f = Omega(g) тогда и только тогда, когда g = O(f).

Answer 2

Асимптотическая оценка - ожидаемое поведение по мере того, как число операций переходит в бесконечность. Математически это так, что lim, когда n уходит в бесконечность. Однако наихудшее поведение применимо к конечному числу операций.

Answer 3

Для примера возьмите quicksort. Каждый последующий рекурсивный вызов п сортировки имеет время выполнения сложности Т (п)

Т (п) = O (N) + 2 T [(п-1)/2]

в ' наилучший случай ", если несортированный входной список разбит на два равных подсписок размера (n-1)/2 в каждом вызове. Решение для T (n) дает O (n log n), в этом случае. Если раздел не является совершенным, и два подсписки не равного размера п, т.е.

Т (п) = О (п) + Т (к) + Т (п - 1 - к),

, мы все равно получаем O (n log n), даже если k = 1, только с большим постоянным множителем. Это связано с тем, что количество рекурсивных вызовов quicksort растет экспоненциально при обработке списка ввода до тех пор, пока k> 0.

Тем не менее, в 'худшем случае' нет разделения входного списка имеет место, то есть:

Т (п) = О (п) + T (0) + T (п - 1) = О (n) + O (n-1) + T (n-1) + T (n-2) ....

Это происходит, например, если мы возьмем первый элемент отсортированного списка в качестве сводного элемента.

Здесь T (0) означает, что один из результирующих подвычислителей равен нулю и, следовательно, не занимает вычислительного времени (так как подвыбор имеет нулевые элементы). Вся оставшаяся нагрузка T (n-1) необходима для второго подсписка. В этом случае получаем O (n²).

Если алгоритм не имеет сценария наихудшего случая, это будет не только O [f (n)], но также o [f (n)] (Big-O vs. little-o notation).