Рекуррентные отношения, алгоритм анализа

Question

Хорошо, у меня есть некоторые трудности с полным пониманием рекуррентных отношений.

Так, например, если я анализирую быструю сортировку в худшем случае, используя Θ-нотацию, давая массиву ввод несортированных положительных чисел;

Когда базовый случай n <= 3, я сортирую небольшой массив, используя вставки сортировки. Время: O (1) или O (n ^ 2)? </p>

Я использую линейный поиск, чтобы установить ось как медиану всех элементов. Время: Θ (н)

Разбиение слева и справа от оси и выполнение рекурсии. Время: 2 * Т (н / 2) Я думаю

будет ли повторение: T (n) = O (1) + Θ (n) + 2 * T (n / 2) тогда?

Что-то подсказывает мне, что базовый случай вместо этого потребует O (n ^ 2) времени, потому что, если ввод достаточно мал, это будет наихудший случай. Это тогда даст мне повторение: T (n) = O (n ^ 2) + Θ (n) + 2 * T (n / 2)?

Answer 1

1. Когда базовый случай n
   • всегда O (1)
2. Я использую линейный поиск, чтобы установить ось как медиану всех элементов.
   • Возможно, вы захотите уточнить это подробнее, чтобы найти медиану, поскольку опорная точка не является простой задачей выполнения линейного поиска. Несколько способов: я) Алгоритм быстрого выбора (среднее значение O (N)) или ii) сортировка подраздела O (NlogN) iii) алгоритм медианы медианы O (N).
3. Разбиение слева и справа от оси и выполнение рекурсии.
   • 2F (N / 2) + N

Собираем все вместе (при условии, что ось всегда является медианой, и что вы берете O (N), чтобы найти ось каждый раз):

Best_Case = Worst_Case (поскольку ось всегда медиана)

F(3) = F(2) = F(1) = 1

F(n) = 2F(N/2) + 2N 
= 2(2F(N/2^2) + 2(N/2)) + 2N 
= 2(2)F(N/2^2) + 2N + 2N
= 2(3)F(N/2^3) + 3(2)N
= 2(LogN)F(N/N) + (2N)LogN
= O(NlogN)