一、补充:递归相关知识
fi𝑏(𝑛) ::= 𝑓𝑖𝑏(𝑛 − 1) 𝑓𝑖𝑏(𝑛 − 2), 𝑛 > 1
| 1 ,𝑛 = 1
| 0 ,𝑛 = 0
int Fib(n){ if(n<=1) return n; else return Fib(n-1) Fib(n-2);}
二、算法的基本概念
有穷性:算法运行的步数是有限的,运行的时间也是有限的 |
确定性:对同一输入每次都有相同的输出 |
可行性:算法中描述的操作都是可以通过已实现的基本运算执行有限次实现 |
输入:有0个或多个输入 |
输出:有1个或多个输出 |
三、好的算法应考虑的目标
正确性:算法能正确的解决问题 |
可读性:算法应具有良好的可读性,以便于人们理解 |
健壮性:也称鲁棒性,当输入非法数据时算法也能适当做出反应或进行处理 |
效率:算法执行的时间尽可能短 |
低存储:算法执行过程中所需要的最大存储空间应尽可能小 |
四、算法的效率度量:时间复杂度和空间复杂度
若f(n) = O(𝑛^logb^(𝑎−𝜀))对于某个𝜀 >0成立,那么T(n) = O(𝑛^log𝑏^𝑎) |
若f(n) = O(𝑛log𝑏^𝑎),那么T(n) = O(𝑛^log𝑏^𝑎 * logn) |
若f(n) = O(𝑛log𝑏^(𝑎 𝜀))对于某个𝜀 >0成立,并且af(n/b)≤cf(n),对于某个常量c<1(n足够大)成立,那么T(n) = O(f(n)) |
//no1理解:比较f(n)与𝑛^log𝑏^𝑎的大小谁大T(n)就取它,相等时T(n) = O(𝑛^log𝑏^𝑎 * logn)T(n) = aT(n/b) f(n)T(n/b) = aT(n/𝑏^2) f(n/b)T(n) = a[ aT(n/𝑏^2) f(n/b) ] f(n) =𝑎2T(n/𝑏^2) af(n/b) f(n)//no2例子:迭代表达式T(n) = 3T(n/2) n^2解析:1.验证是否满足主定理 2.验证满足哪种情况 3.根据主定理求解该迭代式满足主方法比较f(n)与𝑛^log𝑏^𝑎的大小有n^log2^3 < 𝑛^2满足情况第三种且3(𝑛^2)/4 < 𝑐𝑛^2故T(n) = O(𝑛^2)【例子】(2012华中科技大学887)汉诺塔问题 假定move()的时间复杂度为O(1),则下列算法的时间复杂度是 ( )void hanoi(int n,char x,char y,char z){ if(n==1) move(x,1,z); else { hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,x,z,y); } }
联系客服