Асимптотические обозначения и формирование рекуррентных соотношений путем анализа алгоритмов

Я просмотрел множество лекций, видео и источников, касающихся асимптотических обозначений. Я понял, что такое О, Омега и Тета. Но почему в алгоритмах мы всегда используем только нотацию Big Oh, а не тета и омега (знаю, это звучит нубски, но, пожалуйста, помогите мне с этим). Что такое верхняя и нижняя границы в соответствии с алгоритмами?

Мой следующий вопрос: как мы находим сложность алгоритма. Скажем, у меня есть алгоритм, как мне найти рекуррентное отношение T(N) и затем вычислить из него сложность? Как составить эти уравнения? Как и в случае линейного поиска с использованием рекурсивного способа, T(n)=T(N-1) + 1. Как?

Было бы здорово, если бы кто-нибудь объяснил, что я считаю себя нубом, чтобы я мог понять еще лучше. Я нашел несколько ответов, но не был достаточно убедителен в StackOverFlow.

Спасибо.


recurrence algorithm
person Ankur Sinha    schedule 11.08.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Когда мы создаем алгоритм, он всегда делается для того, чтобы быть самым быстрым, и нам нужно учитывать каждый случай. Вот почему мы используем O, потому что мы хотим увеличить сложность и быть уверенными, что наш алгоритм никогда не превзойдет ее.

Чтобы оценить сложность, нужно посчитать количество шагов. В уравнении T(n) = T(n-1) + 1 перед вычислением T(0) будет N шагов, тогда сложность будет линейной. (Я говорю о временной сложности, а не пространственной сложности).

person Jérôme Boé    schedule 11.08.2012

arrow_upward
1
arrow_downward

Почему мы так часто используем big-O по сравнению с Theta и Omega: Это отчасти связано с культурой, а не с техникой. Люди очень часто говорят «большое О», когда тета действительно была бы более подходящей. Омега редко используется на практике, потому что мы часто больше заботимся о верхних границах, чем о нижних, а также потому, что нетривиальные нижние границы часто гораздо труднее доказать. (Тривиальные нижние границы обычно говорят: «Вы должны просмотреть все входные данные, поэтому время выполнения по крайней мере равно размеру входных данных».)

Конечно, эти комментарии о нижних границах также частично объясняют тету, поскольку тета включает в себя как верхнюю, так и нижнюю границу.

Придумать рекуррентное отношение. Не существует простого рецепта, который подходит для всех случаев. Вот описание относительно простых рекурсивных алгоритмов.

Пусть N будет размером начального входа. Предположим, что в вашей рекурсивной функции имеется R рекурсивных вызовов. (Пример: для сортировки слиянием R будет равно 2.) Далее предположим, что все рекурсивные вызовы уменьшают размер начального ввода на одну и ту же величину, с N до M. (Пример: для сортировки слиянием M будет равно N/2.) И, наконец, предположим, что рекурсивная функция W работает вне рекурсивных вызовов. (Пример: для сортировки слиянием W будет N для слияния.)

Тогда рекуррентное соотношение будет T(N) = R*T(M) + W. (Пример: для сортировки слиянием это будет T(N) = 2*T(N/2) + N.)

person Chris Okasaki    schedule 12.08.2012