当前位置：文档之家 › 算法分析基础

算法分析基础

  • 格式：pdf
  • 大小：3.38 MB
  • 文档页数：41

下载文档原格式

  / 41

合集下载

算法设计与分析基础课后习题答案solu4

算法设计与分析基础课后习题答案solu4
Solving it by backward substitutions for n = 2k yields the following:
C(2k) = 2C(2k−1) + 1 = 2[2C(2k−2) + 1] + 1 = 22C(2k−2) + 2 + 1 = 22[2C(2k−3) + 1] + 2 + 1 = 23C(2k−3) + 22 + 2 + 1 = ... = 2iC(2k−i) + 2i−1 + 2i−2 + ... + 1 = ... = 2kC(2k−k) + 2k−1 + 2k−2 + ... + 1 = 2k − 1 = n − 1.
Design a divide-and-conquer algorithm for this problem.
2
Hints to Exercises 4.1
1. In more than one respect, this question is similar to the divide-and-conquer computation of the sum of n numbers. Also, you were asked to analyze an almost identical algorithm in Exercises 2.4.
b. Set up and solve a recurrence relation for the number of multiplications made by this algorithm.
c. How does this algorithm compare with the brute-force algorithm for this problem?

《算法设计与分析基础(第3版)》第一,二章部分习题答案

《算法设计与分析基础(第3版)》第一,二章部分习题答案

作业一学号：_____ 姓名：_____说明：1、正文用宋体小四号，1.5倍行距。

2、报告中的图片、表格中的文字均用宋体五号，单倍行距。

3、图片、表格均需要有图片编号和标题，均用宋体五号加粗。

4、参考文献用宋体、五号、单倍行距，请参照参考文献格式国家标准（GB/T 7714-2005）。

5、公式请使用公式编辑器。

P144.用伪代码写一个算法来求方程ax2+bx+c=0的实根，a，b，c 是任意实系数。

（可以假设sqrt(x)是求平方根的函数。

）算法：Equate(a,b,c)//实现二元一次方程求解实数根//输入：任意系数a，b，c//输出：方程的实数根x1，x2或无解If a≠0p←b2−4acIf p>0x1←−b+sqrt(p)2ax2←−b−sqrt(p)2areturn x1，x2else if p=0return −b2aelsereturn “no real roots”elseif b≠0return −cbelseif c≠0return “no real numbers”elsereturn “no real roots”5.写出将十进制正整数转换为二进制整数的标准算法。

a.用文字描述。

b.用伪代码描述。

a.解：输入：一个正整数n输出：正整数n相应的二进制数第一步：用n 除以2，余数赋给K[i](i=0,1,2...)，商赋给n第二步：如果n=0 ，则到第三步，否则重复第一步第三步：将K[i]按照i从高到低的顺序输出b.解：算法：DecToBin(n)//实现正整数十进制转二进制//输入：一个正整数n//输出：正整数n对应的二进制数组K[0..i]i ←1while n≠0 doK[i]←n%2n←(int)n/2i ++while i≠0doprint K[i]i - -p462.请用O，Ω 和θ的非正式定义来判断下列断言是真还是假。

a. n(n+1)/2∈O(n3)b. n(n+1)/2∈O(n2)c. n(n+1)/2∈θ(n3)d. n(n+1)/2∈Ω(n)解：断言为真：a，b，d断言为假：cP535.考虑下面的算法。

算法设计与分析基础课后习题答案

算法设计与分析基础课后习题答案

Program算法设计与分析基础中文版答案习题5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次..对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n).n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A[0..n-1])n-1]a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element., 0 for an array of positive numbers ) to mark the i th position is empty. (“lazy deletion”)第2章习题7.对下列断言进行证明:(如果是错误的,请举例)a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α>0时,Θ(αg(n))= Θ(g(n))解:a. 这个断言是正确的。

算法设计与分析基础习题参考答案

算法设计与分析基础习题参考答案

算法设计与分析基础习题参考答案5..证明等式gcd(m,n)=gcd(n,m mod n)对每⼀对正整数m,n都成⽴.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d⼀定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意⼀对正整数m,n,若d能整除m和n,那么d⼀定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也⼀定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限⾮空集，其中也包括了最⼤公约数。

故gcd(m,n)=gcd(n,r)6.对于第⼀个数⼩于第⼆个数的⼀对数字,欧⼏⾥得算法将会如何处理?该算法在处理这种输⼊的过程中,上述情况最多会发⽣⼏次? Hint:对于任何形如0<=m并且这种交换处理只发⽣⼀次.7.a.对于所有1≤m,n≤10的输⼊, Euclid算法最少要做⼏次除法?(1次)b. 对于所有1≤m,n≤10的输⼊, Euclid算法最多要做⼏次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—⼭⽺C—⽩菜2.(过桥问题)1,2,5,10---分别代表4个⼈, f—⼿电筒4. 对于任意实系数a,b,c, 某个算法能求⽅程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平⽅根的函数)算法Quadratic(a,b,c)//求⽅程ax^2+bx+c=0的实根的算法//输⼊:实系数a,b,c//输出:实根或者⽆解信息D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将⼗进制整数表达为⼆进制整数的标准算法a.⽤⽂字描述b.⽤伪代码描述解答：a.将⼗进制整数转换为⼆进制整数的算法输⼊：⼀个正整数n输出：正整数n相应的⼆进制数第⼀步：⽤n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第⼆步：如果n=0，则到第三步，否则重复第⼀步第三步：将Ki按照i从⾼到低的顺序输出b.伪代码算法DectoBin(n)//将⼗进制整数n转换为⼆进制整数的算法//输⼊：正整数n//输出：该正整数相应的⼆进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下⾯这个算法,它求的是数组中⼤⼩相差最⼩的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输⼊:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样⼀个排序算法,该算法对于待排序的数组中的每⼀个元素,计算⽐它⼩的元素个数,然后利⽤这个信息,将各个元素放到有序数组的相应位置上去.a.应⽤该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所⽰:b.该算法不稳定.⽐如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[]4.(古⽼的七桥问题)习题1.41.请分别描述⼀下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty . (―lazy deletion ‖)第2章习题2.17.对下列断⾔进⾏证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断⾔是正确的。

算法分析基础——主定理

算法分析基础——主定理

算法分析基础——主定理
对于形为T(n) = aT(n / b) + f(n)的递推⽅程，我们有如下结论：
主定理（MasterTheorem）设a≥1，b>1 为常数，f(n)为函数，n为⾮负整数，且 T(n) = aT(n / b) + f(n)，则有以下结果：
1. 若存在ε>0，使得f(n) = O(n log b a-ε)，则T(n) = Θ(n log b a)
2. 若f(n) = Θ(n log b a)，则T(n) = Θ(n log b a logn)
3. 若存在ε>0，使得f(n) = Ω(n log b a+ε)，并且对于某个常数c<1和所有充分⼤的n，有af(n / b)≤cf(n)，则T(n) = Θ(f(n))
证明：详见教材（推导过程略复杂，不想写了qwq）。

由主定理可以直接得到下述推论：
推论1 依主定理条件，递推⽅程为T(n)= aT(n / b) + c，则
1. 当a≠1时，T(n) = Θ(n log b a)
2. 当a=1时，T(n) = Θ(logn)
推论2 依主定理条件，递推⽅程为T(n) = aT(n / b) + cn，则
1. 当a>b时，T(n) = Θ(n log b a)
2. 当a=b时，T(n) = Θ(nlogn)
3. 当a<b时，T(n) = Θ(n)
例根据主定理及其推论，我们可以直接得到⼆分检索算法的平均时间复杂度为Θ(logn)，⽽⼆分归并排序的平均时间复杂度为Θ(nlogn)。

算法设计与分析基础

算法设计与分析基础

2023/12/21
20
LingJie/GDUT
1.2.6 详细表述该算法的方法
• 可以用到的工具有自然语言（nature
language）、伪代码（pseudocode）以及程序 流程图（flow chart）等。
• 当对一个问题有了概要的理解后，下面的工作
就是把这个问题的想法进行细化。所谓的细化 就是把它们表示成算法的步骤。
令执行顺序以及同步等问题。并行算法的设计 有相应的理论，这里仅考虑串行算法。
2023/12/21
17
LingJie/GDUT
1.2.3 选择精确或者近似的算法
• 解决问题下一步要考虑的是使用精确的还是近
似的算法。并不是每一个可解的问题都有精确 的算法，例如求一个数的平方根，求非线性方 程的解等。有时候一个问题有精确的解法但是 算法的执行效率很差，例如旅行家问题。因此 如果待处理的问题涉及到上述那些方面，则要 考虑是选择精确的还是近似的算法。
2023/12/21
10
LingJie/GDUT
-- 2* 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
-- 2 3*
5
7
9
11
13
15
17
19
21
23
25
-- 2 3
5*
7
11
13
17
19
23
25
-- 2 3
5
7
11
13
第一步：找出m的所有质因数。 第二步：找出n的所有质因数。 第三步：从第一步求得的m的质因数分解式和第二步求得的n
的质因数分解式中，找出所有公因数。 第四步：将第三步找到的公因数相乘，结果为所求的

算法-第2章-算法效率分析基础


The Big-O and Related Notations
2.2.7 基本的效率类型
1 log n n n log n n2 n3 2n n! constant logarithmic linear n log n quadratic cubic exponential factorial
思考
2.2.2 符号О
定义1 我们把函数t(n)属于O(g(n)) ，记作t(n) ∈ O(g(n)) ; 它的成立条件是：对于所有足够大的n， t(n) 的上界由g(n) 的常数倍数所确定，也就是说，存在大于0的常数c和非负 的整数n0，使得： 对于所有的n≥ n0来说， t(n) ≤c g(n)
cg(n)
2.2 渐进符号和基本效率类型
2.2.1 非正式的介绍
O(g(n)) 是增长次数小于等于g(n) (以及其常数倍，n趋 向于无穷大)的函数集合。 n∈O(n2),100n+5∈O(n2), n(n-1) /2 ∈O(n2),n3∈/ O(n2), Ω(g(n))，代表增长次数大于等于g(n)(以及其常数倍,n趋 向于无穷大)的函数集合。 n3∈ Ω(n2)， n(n-1) /2 ∈ Ω(n2)，但是100n+5 ∈/ Ω(n2) Θ(g(n))是增长次数等于g(n) )(以及其常数倍,n趋向于无 穷大)的函数集合。因此，每一个二次方程an2+bn+c在 a>0的情况下都包含在Θ(n2)中，除了无数类似于n2+sin n和n2+log n的函数（你能解释原因吗？）。
t(n) cg(n)
n0之前的情 况无关重要
n n0 符号Ω：t(n)∈Ω(g(n))
2.2.4 符号Θ
定义 3 我们把函数t(n)属于Θ(g(n)) ，记作t(n) ∈Θ(g(n)) ; 它的成立条件是：对于所有足够大的n， t(n) 的上界和下 界都由g(n)的常数倍数所确定，也就是说，存在大于0的 常数c1，c2和和非负的整数n0，使得： 对于所有的n≥ n0来说， c2g(n) ≤t(n) ≤ c1g(n)

第2章 算法分析基础(《算法设计与分析(第3版)》C++版 王红梅 清华大学出版社)


3
Page 11
2.1.2 算法的渐近分析
常见的时间复杂度：
Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)
多项式时间，易解问题
算
法
指数时间，难解问题
设 计 与
分
析
（
第
时间复杂度是在不同数量级的层面上比较算法
版 ）
清
华
大
学
时间复杂度是一种估算技术（信封背面的技术）
Page 7
2.1.2 算法的渐近分析
3
每条语句执行次数之和 = 算法的执行时间 ＝ 每条语句执行时间之和
基本语句的执行次数 for (i = 1; i <= n; i++)
单位时间
算
法
设
计
与
执行次数 × 执行一次的时间
分 析 （
第
for (j = 1; j <= n; j++)
版 ）
x++;
指令系统、编译的代码质量
算法设计：面对一个问题，如何设计一个有效的算法
算
法
设
检
指
验
导
评
计 与 分 析 （ 第 版
改
估
） 清
进
华 大
学
出
版
算法分析：对已设计的算法，如何评价或判断其优劣
社
3
Page 3
2.1.1 输入规模与基本语句
如何度量算法的效率呢？
事后统计：将算法实现，测算其时间和空间开销
缺点：（1）编写程序实现算法将花费较多的时间和精力 （2）所得实验结果依赖于计算机的软硬件等环境因素

第2章 算法分析基础ppt课件

•事后测试：将算法编制成程序后放到计算机上运行，收集 其执行时间和空间占用等统计资料，进行分析 判断——直接与物理实现有关。
最新课件
7
1）事前分析
• 目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法 “好坏”。
• 如何给出反映算法执行特性的描述？
最直接方法：统计算法中各种运算的执行情况：
算法的数量级从本质上反映了一个算法的执行特性。 例：求解同一问题的三个算法分别具有n, n2 , n3数量级。 若n=10，则可能的执行时间将分别是10，100，1000 个 单位时间——与环境因素无关。
最新课件
10
• 计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）
的一个函数表示形式，一般记为与输入规模n有关 的函数形式：f(n)
则记作 f(N)=(g,(N))
含义：
• 算法在最好和最坏情况下的计算时间就一个常数因子范 围内而言是相同的。可看作：
既有f(N)=Ω(g(N))，又有f(N)=Ο(g(N))
最新课件
28
最新课件
29
算法分析方法
• 例：顺序搜索算法
template<class Type> int seqSearch(Type *a, int n, Type k) {
最新课件
13
算法的时间复杂性
• （1）最坏情况下的时间复杂性 • Tmax(n) = max{ T(I) | size(I)=n } • （2）最好情况下的时间复杂性 • Tmin(n) = min{ T(I) | size(I)=n } • （3）平均情况下的时间复杂性
• Tavg(n) =
p(I)T(I)

算法分析基础


6
程序(Program)
• 程序是算法用某种程序设计语言的具体实现。 • 程序可以不满足算法的有限性的性质。例如操作系统，是一个
在无限循环中执行的程序，因而不是一个算法。 • 操作系统的各种任务可看成是单独的问题，每一个问题由操作
系统中的一个子程序通过特定的算法来实现。该子程序得到输 出结果后便终止。
《算法设计技巧与分析》
第1章 算法分析基本概念
曹霑懋 caozhanmao@
Chapter 1 Basic Concepts in Algorithmic Analysis 内容
1.1 Introduction l.2 Historical Background 1.3 Binary Search 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 1.5 Selectinn Sort 1.6 Insertion Sort 1.7 Bottom-Up Merge Sorting 1.7.1 Analysis of bottom-up merge sorting
最大搜索次数：满足Floor(n/2j-1)=1 时的ｊ 值
– 即：１n/2j-1 <2 – 也即： 2j-1n <2j
– j-1 log n <j
j=Floor(log n)+1
2020/6/10
华南师范大学 计算
16
设随有堂序数练组习：
试搜索x=20, 以及 X =22. 1）拟用什么法？为什么？ 2）试给出用你想要得算法求解的过程。
2020/6/10
华南师范大学 计算
14
1. 3 二分搜索及其时间复杂
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

称为该序列的通项。
例：序列{‫}࢔ܠ‬，‫ = ࢔ܠ‬૚/࢔。
૚，
૚ ૛
，
૚ ૜
，
…
…
等比序列是形如 ‫܉‬, ‫ܙ܉‬, ‫ܙ܉‬૛, … , ࢇࢗ࢔
例：-1，1，-1，1，-1，……
10，50，250，1250，……
通项公式：ࢇ࢔ = ‫܉‬૚ ∗ ‫ܖܙ‬−૚
求和公式：‫܉ ∗ ܖ = ܖ܁‬૚ ሺ‫ = ܙ‬૚ሻ
13
2014-9-29 14
2014-9-29
=>
15
2014-9-29
1 算法分析和设计过程 2 常用算法分析中的数学公式 3 非递归算法的数学分析 4 递归算法的数学分析 5 递推关系（Recurrence Relations）
◦ 5.1 序列 ◦ 5.2 递推关系的求解方法 ◦ 5.3 常见递推类型*
前向替换法 反向替换法 二阶常系数线性递推式
19
2014-9-29
从初始条件给出的序列初始项开始，采用递推方程 生成的前几项，然后从中找出一个能够使用闭合公 式表示的模式。
例如：
x(n)=2x(n−1)+1 x(1)=1
for n>1, (5) (6)
x(1)=1 x(2)=2x(1)+1=2*1+1=3, x(3)=2x(2)+1=2*3+1=7, x(4)=2x(3)+1=2*7+1=15.
x(n)=2^n−1
for n=1,2,3,and 4.
x(n)=x(n-1)+n, n>0 x(0)=0
(1) 递推关系 (2) 初始条件
x(n)=x(n−1)+n. x(n)=[x(n−2)+n−1]+n=x(n−2)+(n−1)+n x(n)=[x(n−3)+n−2]+(n−1)+n=x(n−3)+(n−2)+(n−1)+n. ...... x(n)=x(n−i)+(n−i+1)+(n−i+2)+...+n x(n)=x(0)+1+2+...+n=0+1+2+...+n=n(n+1)/2.
9
2014-9-29
基本操作
输入规模：n 基本操作：最内层的比较操作
10
2014-9-29
研究最差情况的效率问题 如果对于每一个数组所做的比较Cworst(n)比其他数组都多， 那么它是所有大小为n的数组中的最差输入。 两种类型最差输入： 1. 不含有相同元素的数组 2. 最后两个元素是唯一一对相同元素的数组
‫ܖ܁‬
=
‫܉‬૚ሺ૚ − ‫ܖܙ‬ሻ ૚−‫ܙ‬
ሺ‫ܙ‬
≠
૚ሻ
17
2014-9-29
等差序列形如 a,a+d,a+2d,…,a+nd
例：-1，3，7，11，……
7，4，1，-2，……
通项公式：ࢇ࢔ = ‫܉‬૚ + ሺ‫ ܖ‬− ૚ሻ ∗ ‫܌‬ ࢇ࢔ = ‫ ܕ܉‬+ ሺ‫ ܖ‬− ‫ܕ‬ሻ ∗ ‫܌‬ 求和公式：
21
2014-9-29
定理 1：设 r1,r2 是递推关系(8)的特征方程(9)的两个根。 情况 1：如果 r1,r2 是不相等的实根，递推式(8)的通解由以下公式给出
‫ܠ‬ሺ‫ܖ‬ሻ = હ‫ܚ‬૚‫ ܖ‬+ ઺‫ܚ‬૛‫ܖ‬ αβ为两个任意的实常数 情况 2：如果 r1,r2 相等，递推式(8)的通解由以下公式给出
2014-9-29
2014年9月29日Monday
1 算法分析和设计过程 2 常用算法分析中的数学公式 3 非递归算法的数学分析 4 递归算法的数学分析 5 递推关系（Recurrence Relations） 6 数学归纳法 7 递归和结构归纳法
1
2014-9-29 We can consider algorithms to be procedural solutions to problems. These solutions are not answers but specific instructions for getting answers.
2014-9-29
递推方程的通解：一个能够指出所有这种序列的公式。
通常情况下一个通解包含多个任意常数。
‫ ܖ（ܖ‬+ ૚）
‫ܠ‬ሺ‫ܖ‬ሻ = ‫ ܋‬+
૛
其中，c 是任意常数。如果 c 赋予不同的值，就可以得到方程(1)的所有解。
特解：一个满足给定递推方程的特定序列。
通常感兴趣的是满足初始条件的特解。
ࡿ࢔
=
ሺ‫܉‬૚
+ ‫ܖ܉‬ሻ ૛
∗
‫ܖ‬
a 和 d 都为实数
方法1：定义序列的通项。
如，x(n)=2*n，n>=0
方法2：用一个方程把它的通项和该序列的一个或 者多个其它项关联起来，并且提供首项的精确值。
例如: x(n)=x(n-1)+n, n>0 x(0)=0
(1) 递推关系 (2) 初始条件
18
√૞
√૞
૚ ૚ + √૞ ࢔ ૚ ૚ − √૞ ࢔
说明：对于大多数简单的递推关系，上述方法有效。
20
2014-9-29
形如： ax(n)+bx(n−1)+cx(n−2)=f (n), (7) 其中，a!=0
二阶: 在未知序列中，元素x(n)和x(n-2)差两个位置
线性: 递推式的左边部分都是序列未知项的一个线性组合
常系数：a,b,c都是固定实数
如果对于每个f(n)=0，则递推式是齐次的，否则为非齐次。
6 数学归纳法 7 递归和结定义：一个（数值）序列是有序数字的一个列表 。
例如：2，4，6，8，10……(正偶数)
0，1，1，2，3，5，8……(Fibonacci)
常用带下标的字母放在大括号中，表示一个序列，如{xn}或者 x(n)。 序列就是函数，自变量为 n，函数值 x(n)代表序列中数字本身。x(n)被
‫ܠ‬ሺ‫ܖ‬ሻ = હ‫ ܖܚ‬+ ઺‫ܖܚܖ‬ 其中 r=r1=r2 ,αβ为两个任意的实常数 情况 3：如果 r1,r2 是不相等的复数，递推式(8)的通解由以下公式给出
‫ܠ‬ሺ‫ܖ‬ሻ = ‫[ܖܚ‬હ‫ܖܛܗ܋‬ી + ઺‫ܖܖܑܛ‬ી] 其中，઻ = √‫ܝ‬૛ + ‫ܞ‬૛ ，ી = ‫ܞܖ܉ܜ܋ܚ܉‬/‫ܝ‬，αβ为两个任意的实常数
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181， 6765，10946，17711，28657，46368 意大利数学家Leonardo Fibonacci(1170-1250)。 1202年，他撰写了《算盘全书》（Liber Abacci） 一书。他是第一个研究了印度和阿拉伯数学理论的 欧洲人。他的父亲被比萨的一家商业团体聘任为外 交领事，派驻地点相当于今日的阿尔及利亚地区， 列昂纳多因此得以在一个阿拉伯老师的指导下研究 数学。他还曾在埃及、叙利亚、希腊、西西里和普 罗旺斯等地研究数学。
Fibonacci 递推式的特征方程为 ‫ܚ‬૛ − ‫ ܚ‬− ૚ = ૙
૚ ± ඥ૚ − ૝ሺ−૚ሻ ૚ ± √૞
‫ܚ‬૚,૛ =
૛
=૛
由于该方程有两个不相等的实根，所以根据定理 1
࢔
࢔
૚ + √૞
૚ − √૞
ࡲሺ࢔ሻ = ࢻ ቆ ૛ ቇ + ࢼ ቆ ૛ ቇ
将初始条件带入确定αβ的具体值
ࡲሺ࢔ሻ
2
2014-9-29
理解问题 了解计算设备的性能* 在精确解法和近似解法之间选择 确定适当的数据结构（程序=算法+数据结构） 算法设计技术（算法解题的一般性方法） 详细表述算法的方法（伪代码、流程图） 证明算法的正确性* 分析算法（时间效率、空间效率和一般性） 为算法写代码
大多数的算法运行于冯.诺伊曼的计算机体系结构， 此结构的重点是随机存取机（RAM）。 指令逐条执行，每次执行一条操作，基于此机器上 的算法成为顺序算法。 如果同一时间执行多条操作，即并行计算；相应的 算法为并行算法。 算法的研究应该独立于特定机型平台。
x(n)-6x(n-1)+9x(n-2)=0 特征方程为‫ܚ‬૛ − ૟‫ ܚ‬+ ૢ = ૙ 有两个相等的根 r1=r2=3， 因此属于定理 1 的情况 2 通解是由公式
‫ܠ‬ሺ‫ܖ‬ሻ = હ૜‫ ܖ‬+ ઺‫ܖ‬૜‫ܖ‬ 如果知道初始条件，如 x(0)=0 和 x(1)=3, 我们把 n=0 和 n=1 代入最后一个方程。 得到α=0，β=1。 所以， 递推式特解 ‫ܠ‬ሺ‫ܖ‬ሻ = ‫ܖ‬૜‫ܖ‬
11
2014-9-29 12
2014-9-29
1 算法分析和设计过程 2 常用算法分析中的数学公式 3 非递归算法的数学分析 4 递归算法的数学分析 5 递推关系（Recurrence Relations） 6 数学归纳法 7 递归和结构归纳法
通用方案 1. 决定使用哪个参数作为输入规模的度量 2. 找出算法的基本操作 3. 检查一下，对于相同规模的不同输入，基本操作 的执行次数是否不同。如果不同，则必须对最差效 率、平均效率以及最优效率单独研究。 4. 对于算法基本操作的执行次数，建立一个递推关 系以及相应的初始条件。 5. 解此递推式，或者至少确定它的解的增长次数。
4
2014-9-29 5
2014-9-29 6
2014-9-29 7
2014-9-29 8