java - 找到算法java的递归方程

Question

我真的不知道如何找到算法的递归方程我已经阅读了关于这个主题的其他问题，但有些东西我仍然没有得到。例如在下面的代码中（实际上是伪代码:)）：

MergeSort(list "L" of "n" elements):
if n=<1 then return L
L1 <- MergeSort(L1... n/2)
L2 <- MergeSort(L(n/2 +1) ... n)
L <- Merge(L1, L2) 
return L 

递归方程如下： T(1) = b T(n) = c1 + c2.n + 2T(n/2)

我不明白什么是 c1、c2 和 b 谢谢你的帮助

Answer 1

对 n 个元素进行合并排序：

1. 如果 n = 1 ，则返回孤立元素。
2. 否则，递归排序 [1...n/2] 个元素和 [n/2+1...n] 个元素。
3. 合并 2 个排序的数组。

让对一个包含n 个元素的数组进行归并排序所花费的总时间为T(n)。我们知道基本情况是如果元素的数量n是1，那么我们不需要应用归并排序算法，我们可以只返回那个元素。

if n=<1 then return L

这将需要一个恒定的时间，比如c1。

如果元素大于1，则将数组从[1..n/2]和[n/2+1...n]拆分并递归合并排序。

L1 <- MergeSort(L1... n/2)
L2 <- MergeSort(L(n/2 +1) ... n)

因此，当我们假设合并排序n 个元素所花费的时间是T(n) ，那么对包含大约n/2 个元素的每个子数组进行排序所花费的时间将是T(n/2)。

我们需要在排序后合并子数组，合并n 个元素所花费的时间将是n的线性函数，即c2.n其中c2是将元素放置在最终排序数组中的特定位置所花费的常数时间。