Разве анализ в худшем случае не равен асимптотическим границам? - PullRequest
3 голосов
/ 24 января 2011

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

Ответы [ 3 ]

4 голосов
/ 24 января 2011

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

Вы можете иметь асимптотику в худшем случае . Если 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).

0 голосов
/ 24 января 2011

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

T (n) = O (n) + 2 T [(n-1) / 2]

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

T (n) = O (n) + T (k) + T (n - 1 - k),

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

Однако в «наихудшем случае» деление входного списка не происходит, т. Е .:

T (n) = O (n) + T (0) + T (n - 1) = O (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 против little-o нотации ).

0 голосов
/ 24 января 2011

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

...