计算机算法设计与分析（第3版） 王晓东 编著 电子工业出版社.

Presentation on theme: "计算机算法设计与分析（第3版） 王晓东 编著 电子工业出版社."— Presentation transcript:

1 计算机算法设计与分析（第3版） 王晓东 编著 电子工业出版社

2 第1章 算法概述 学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。
第1章 算法概述 学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C++语言描述算法的方法。

3 算法(Algorithm) 算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质：
(1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

4 程序(Program) 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。
例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

5 问题求解(Problem Solving)
理解问题 精确解或近似解 选择数据结构 算法设计策略 设计算法

6 算法复杂性分析 算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。

7 算法的时间复杂性 （1）最坏情况下的时间复杂性 Tmax(n) = max{ T(I) | size(I)=n }
（2）最好情况下的时间复杂性 Tmin(n) = min{ T(I) | size(I)=n } （3）平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。

8 算法渐近复杂性 T(n)  , as n ; (T(n) - t(n) )/ T(n) 0 ，as n;
在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简单。

9 渐近分析的记号 在下面的讨论中，对所有n，f(n)  0，g(n)  0。 （1）渐近上界记号O
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0  f(n)  cg(n) } （2）渐近下界记号  (g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n)  f(n) }

10 （3）非紧上界记号o o(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n n0有：0  f(n)<cg(n) } 等价于 f(n) / g(n) 0 ，as n。 （4）非紧下界记号  (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n n0有：0  cg(n) < f(n) } 等价于 f(n) / g(n)  ，as n。 f(n)   (g(n))  g(n)  o (f(n))

11 （5）紧渐近界记号  (g(n)) = { f(n) | 存在正常数c1,c2和n0使得对所有n n0有：c1g(n)  f(n)  c2g(n) } 定理1：  (g(n)) = O (g(n))   (g(n))

12 渐近分析记号在等式和不等式中的意义 f(n)= (g(n))的确切意义是：f(n)  (g(n))。
一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的某个函数。 例如：2n2 + 3n + 1 = 2n2 + (n) 表示 2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某个函数。 等式和不等式中渐近记号O,o, 和的意义是类似的。

13 渐近分析中函数比较 f(n)= O(g(n))  a  b; f(n)= (g(n))  a  b;

14 渐近分析记号的若干性质 （1）传递性： f(n)= (g(n))， g(n)= (h(n))  f(n)= (h(n))；
f(n)= O(g(n))， g(n)= O (h(n))  f(n)= O (h(n))； f(n)= (g(n))， g(n)=  (h(n))  f(n)= (h(n))； f(n)= o(g(n))， g(n)= o(h(n))  f(n)= o(h(n))； f(n)= (g(n))， g(n)=  (h(n))  f(n)=  (h(n))；

15 （2）反身性： f(n)= (f(n))； f(n)= O(f(n))； f(n)= (f(n)). （3）对称性： f(n)= (g(n))  g(n)=  (f(n)) . （4）互对称性： f(n)= O(g(n))  g(n)=  (f(n)) ； f(n)= o(g(n))  g(n)=  (f(n)) ；

16 （5）算术运算： O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ； O(f(n))+O(g(n)) = O(f(n)+g(n)) ； O(f(n))*O(g(n)) = O(f(n)*g(n)) ； O(cf(n)) = O(f(n)) ； g(n)= O(f(n))  O(f(n))+O(g(n)) = O(f(n)) 。

17 规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明：
对于任意f1(n)  O(f(n)) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n)  c1f(n) 。 类似地，对于任意g1(n)  O(g(n)) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n)  c2g(n) 。 令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。 则对所有的 n  n3，有 f1(n) +g1(n)  c1f(n) + c2g(n)  c3f(n) + c3g(n)= c3(f(n) + g(n))  c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) .

18 算法渐近复杂性分析中常用函数 （1）单调函数 单调递增：m  n  f(m)  f(n) ;
（2）取整函数  x  ：不大于x的最大整数；  x  ：不小于x的最小整数。

19 取整函数的若干性质 x-1 <  x   x   x  < x+1；  n/2  +  n/2  = n;
对于n  0，a,b>0，有：   n/a  /b  =  n/ab  ;   n/a  /b  =  n/ab  ;  a/b   (a+(b-1))/b;  a/b   (a-(b-1))/b; f(x)=  x  , g(x)=  x  为单调递增函数。

20 （3）多项式函数 p(n)= a0+a1n+a2n2+…+adnd； ad>0; p(n) = (nd); f(n) = O(nk)  f(n)多项式有界； f(n) = O(1)  f(n)  c; k  d  p(n) = O(nk) ; k  d  p(n) = (nk) ; k > d  p(n) = o(nk) ; k < d  p(n) = (nk) .

21 （4）指数函数 对于正整数m,n和实数a>0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a>1  an为单调递增函数; a>1   nb = o(an)

22 ex  1+x; |x| 1  1+x  ex  1+x+x2 ; ex = 1+x+ (x2), as x0;

23 （5）对数函数 log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a>0,b>0,c>0

24

25 |x| 1  for x > -1, for any a > 0, ,  logbn = o(na)

26 （6）阶层函数 Stirling’s approximation

27

28 算法分析中常见的复杂性函数

29 小规模数据

30 中等规模数据

31 用c++描述算法

32 （1）选择语句： （1.1) if 语句： （1.2) ？语句： if (expression) statement;
（1.2) ？语句： if (expression) statement; else statement; exp1?exp2:exp3 y= x>9 ? 100:200; 等价于： if (x>9) y=100; else y=200;

33 （1.3) switch语句： switch (expression) { case 1: statement sequence; break; case 2:  default: }

34 （2）迭代语句： （2.1) for 循环： for (init;condition;inc) statement;
（2.2) while 循环： while (condition) statement; （2.3) do-while 循环： do{ statement; } while (condition);

35 （3）跳转语句： （3.1) return语句： return expression; （3.2) goto语句： goto label;
 label:

36 （4）函数： 例： return-type function name(para-list) { body of the function
} int max(int x,int y) { return x>y?x:y; }

37 （5）模板template ： template <class Type> Type max(Type x,Type y) {
return x>y?x:y; } int i=max(1,2)； double x=max(1.0,2.0)；

38 （6）动态存储分配： （6.1）运算符new ： 运算符new用于动态存储分配。 new返回一个指向所分配空间的指针。
例：int x；y=new int；y=10； 也可将上述各语句作适当合并如下： int y=new int；y=10； 或 int y=new int(10)； 或 int y；y=new int(10)；

39 （6.2）一维数组 ： 为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。 例： float x=new float[n]； 创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。 然后可用x[0]，x[1]，…，x[n-1]来访问每个数组元素。

40 （6.3）运算符delete ： 当动态分配的存储空间已不再需要时应及时释放所占用的空间。 用运算符delete来释放由new分配的空间。
例： delete y； delete [ ]x； 分别释放分配给y的空间和分配给一维数组x的空间。

41 创建类型为Type的动态工作数组，这个数组有rows行和cols列。
（6.4）动态二维数组 ： 创建类型为Type的动态工作数组，这个数组有rows行和cols列。 template <class Type> void Make2DArray(Type** &x,int rows, int cols) { x=new Type*[rows]; for (int i=0;i<rows;i++) x[i]=new Type[cols]; }

42 当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。
释放空间后将x置为0，以防继续访问已被释放的空间。 template <class Type> void Delete2DArray(Type** &x,int rows) { for (int i=0;i<rows;i++) delete []x[i]; delete []x; x=0; }

43 算法分析方法 例：顺序搜索算法 template<class Type>
int seqSearch(Type *a, int n, Type k) { for(int i=0;i<n;i++) if (a[i]==k) return i; return -1; }

44 （1）Tmax(n) = max{ T(I) | size(I)=n }=O(n)
（2）Tmin(n) = min{ T(I) | size(I)=n }=O(1) （3）在平均情况下，假设： (a) 搜索成功的概率为p ( 0  p  1 )； (b) 在数组的每个位置i ( 0  i < n )搜索成功的概率相同，均为 p/n。

45 算法分析的基本法则 非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环
循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。

46 template<class Type>
void insertion_sort(Type *a, int n) { Type key; // cost times for (int i = 1; i < n; i++){ // c n key=a[i]; // c n-1 int j=i-1; // c n-1 while( j>=0 && a[j]>key ){ // c sum of ti a[j+1]=a[j]; // c sum of (ti-1) j--; // c sum og (ti-1) } a[j+1]=key; // c n-1

47 在最好情况下，ti=1, for 1  i <n;
在最坏情况下，ti  i+1, for 1  i <n;

48 对于输入数据a[i]=n-i,i=0,1,…,n-1，算法insertion_sort 达到其最坏情形。因此，
由此可见，Tmax(n)= (n2)

49 最优算法 问题的计算时间下界为(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。
例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。

50 递归算法复杂性分析 int factorial(int n) { if (n == 0) return 1;
return n*factorial(n-1); }

51