algorithm - 递归关系，分析算法

Question

好吧，我很难完全理解递归关系。

例如，如果我使用 Θ 符号分析最坏情况下的快速排序，则为数组提供未排序的正数输入；

当基本情况 n <= 3 时，我使用插入排序对小数组进行排序。时间:O(1) 还是 O(n^2)？

我使用线性搜索将枢轴设置为所有元素的中位数。时间:Θ(n)

分割主元左右并进行递归。时间:2 * T(n/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 <= 3 时，我使用插入排序对小数组进行排序。
   • 总是O(1)
2. 我使用线性搜索将枢轴设置为所有元素的中位数。
   • 您可能想进一步澄清这一点，找到中位数作为枢轴并不是一项简单的线性搜索任务。几种方法是 i) 使用快速选择算法(平均 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)