}
汉诺塔递归算法复杂度分析
输入规模：盘子的数量n 基本操作：移动盘子 执行次数：M(n)
递推式： 当n>1时，M(n)=M(n-1)+1+M(n-1) n=1时，M(n)=1
解递推方程，得解为M(n)=2n-1
2.1 递归的概念
例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…，
第2章 递归与分治策略
算法总体思想
• 将题对仍要。这然求k不解个够的子小较问，大题规则分模再别的划问求分题解为分。k割如个成果子k个子问更问题小题，规的如模的规此子模递问 归的进行下去，直到问题规模足够小，很容易 求出其解为止。
=n T(n)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
算法总体思想
if(n==0)
return 1;
else
用于计算
return F(n-1)*n; F(n-1)
基本操作：乘法
执行次数：M(n)
分析：当n>0时，M(n)=M(n-1)+1
当n=0时，M(0)=0 (初始条件）
求解递推方程，M(n)=n
将F(n-1) 乘以n
汉诺塔问题
设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆 盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘 从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆 盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时 应遵守以下移动规则：
算法mergeSort的递归过程可以消去。 初始序列 [49] [38] [65] [97] [76] [13] [27]
第一步 第二步
[38 49] [65 97] [13 76] [27]
[38 49 65 97]
[13 27 76]
第三步
[13 27 38 49 65 76 97]
合并排序
最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n) 稳定性：稳定
别对2个子集合进行排序，最终将排好序的子集合合并成为所
要求的排复好杂序度的分集析合。

O(1)
n 1
public {
static
void
Tm(en)rgeS2Tor(nt(/C2o)m Opa(nra) bnlea1[],
int
left,
int
right)
if (left<righTt()n{)/=/至O(少nl有og2n个) 渐元进素意义下的最优算法
被称为Fibonacci数列。它可以递归地定义为：

1
n0
F
(n)


1
n 1
F (n 1) F (n 2) n 1
第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n)
{ if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2);
例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。
例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。
规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘
之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至
a,b,c中任一塔座上。
2.1 递归的概念
例2 Hanoi塔问题 在当pu问nb=l题ic1时规sta，模ti问c较v题大oi比时d h较，a简较no单难i(i。找nt此到n,时一in，般t a只的, i要n方t 将法b,编，in号t因c为此) 1我的们圆尝盘试从塔座a 用直递接{ 归移技至术塔来座解b上决即这可个。问题。 当较大n小圆＞的盘i{f1圆从(时n盘塔，> 依座0需)照a要移移利至动用塔规塔座则座b从，c作塔最为座后辅a，移助再至塔设塔座法座。将c此，n时-然1若个后能较，设小将法的剩将圆下n盘的-1依最个 照移动规ha则no从i(塔n-1座, ac移, c至, b塔); 座b。 由此可见mo，vne(个a,圆b)盘; 的移动问题可分为2次n-1个圆盘的移动问题， 这又可以ha递no归i(地n-1用, c上, 述b, 方a)法; 来做。由此可以设计出解Hanoi塔问 题的递} 归算法如下。
缺点：递归算法的运行效率较低，无论是耗费 的计算时间还是占用的存储空间都比非递归 算法要多。
递归小结
解决方法：在递归算法中消除递归调用，使其转 化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用 工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化 效果不明显。
算法总体思想
• 将求出的小规模的问题的解合并为一个更大规 模的问题的解，自底向上逐步求出原来问题的 解。
T(n)
=n
n/2
n/2
n/2
n/2
T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4
• 对将这求k出个的子问小题规分模别的求问解题。如的果解子合问并题为的一规模个仍更然大不规够 小模，的则问再题划的分解为，k个自子底问向题，上如逐此步递求归出的原进行来下问去题，的直 到解问。题规模足够小，很容易求出其解为止。
T(n)
=n
n/2
n/2
n/2
n/2
T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4
人们从大量实践中发现，在用分治法设计算法时，最好使子 问题的规模大致相同。即将一个问题分成大小相等的k个子问题 的处理方法是行之有效的。这种使子问题规模大致相等的做法 是出自一种平衡(balancing)子问题的思想，它几乎总是比子问 题规模不等的做法要好。
合并排序
基本思想：将待排序元素分成大小大致相同的2个子集合，分
int i=(left+right)/2; //取中点
mergeSort(a, left, i);
mergeSort(a, i+1, right);
merge(a, b, left, i, right); //合并到数组b
copy(a, b, left, right); //复制回数组a
}
}
合并排序
问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的
解； 该问题所分解出的各个子问题是相互独立的，即子问
题之间不包含公共的子问题。
因这能为条否问特利题征用的是分涉计应治及算用法到复分完杂治全性法取一的决般前于效是提问率随，题着它是如问也否果题是具各规大有子模多这问的数条题增问特是加题征不， 而可如独增以果立加满具的，足备因的了则此，前分大此两治部特条法分征特要问反征做题映，许满了而多足递不这归具必个思备要特想第的征的三工。应条作用特，征重，复则地 可解以公考共虑的子贪问心题算，法此或时动虽态然规也划可。用分治法，但一般 用动态规划较好。
算法总体思想
• 将求出的小规模的问题的解合并为一个更大规 模的问题的解，自底向上逐步求出原来问题的 解。
分分治割T法成(n的一) 设 些计 规思 模想 较是小=，的将相一同n个问难题以，直以接便解 各决 个的 击大 破问 ，题，
分而治之。
凡治众如治寡，分数是也。
n/2
n/2
n/2 ----孙子兵n/2法

1
q(n,
m)

Байду номын сангаас

q(n, n) 1 q(n, n 1)
q(n, m 1) q(n m, m)
n 1, m 1 nm nm
n m 1
正整数n的划分数p(n)=q(n,n)。
递归小结
优点：结构清晰，可读性强，而且容易用数学 归纳法来证明算法的正确性，因此它为设计 算法、调试程序带来很大方便。
((13)) qq((nn,,1n))==11,+nq1(n; ,n-1); 当即正最整n 大数1n加1的数n划n1分1不由大n于1=1n时的，划任分何和正n1整≤数n-n1只的有划一分种组划成分。形式，
(24) q(n,m)=q(n,nm)-,m1)+nq; (n-m,m),n>m>1; 最正大整加数数n的n1最实大际加上数不n能1不大大于于n。m的因划此分，由q(n11,m=m)=的1。划分和 n1≤n-1 的划分组成。
T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4
2.1 递归的概念
直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。
private static void qSort(int p, int r)
思考题：给定有序表A[1:n]，修 改合并排序算法，求出该有序表 的逆序对数。