PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

菀仰
5 years ago
Views:

计算机算法设计与分析中国科学技术大学信息科学技术学院自动化系王子磊 zlwang@ustc.

1 计算机算法设计与分析中国科学技术大学信息科学技术学院自动化系王子磊

教材计算机算法设计与分析 ( 第 4 版 ) 王晓东编著电子工业出版社 http://www.phei.com.

2 教材计算机算法设计与分析 ( 第 4 版 ) 王晓东编著电子工业出版社教辅 : 教学 :

3 参考书算法导论 Thomas H.Cormen,Charles E.Leiserson, Ronald L.Rivest,Clifford Stein (CLRS) 机械工业出版社计算机程序设计艺术 :The Art of Computer Programming 编著 :Donald Ervin Knuth 国防工业出版社

4 课程要点算法设计思想算法分析方法数据结构及其算法优化算法思想在实际问题中的应用经典算法的设计与分析

5 USTC Chapter 0 Introduction to algorithm 王子磊 (Zilei Wang) zlwang@ustc.edu.cn

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

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

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

9 问题求解 (Problem solving) 理解问题精确解或近似解选择数据结构算法设计策略设计算法证明正确性分析算法设计程序

10 算法复杂性分析计算机程序的性能和所用资源的理论分析算法复杂性 = 算法所需要的计算机资源算法的时间复杂性 T(n) 算法的空间复杂性 S(n) 其中 n 是问题的规模 ( 输入大小 ) 性能之外 Modularity User-friendliness Correctness Programmer time Maintainability Simplicity Functionality Extensibility Robustness Reliability

11 为什么要研究算法复杂性帮助我们理解算法的可扩展性性能通常刻画了可行与不可行之间的界限算法的数学分析为讨论算法行为提供了一种工具程序性能分析的经验能够推广到其他计算资源的分析上速度分析很有意思!

12 排序问题举例 Input: sequence <a 1, a 2,, a n > of numbers. Output: permutation <a' 1, a' 2,, a' n > such that a' 1 a' 2 a' n Example: Input: Output:

13 插入排序

14 插入排序示例

15 插入排序示例

16 插入排序示例

17 插入排序示例

18 插入排序示例

19 插入排序示例

20 插入排序示例

21 插入排序示例

22 插入排序示例

23 插入排序示例

24 插入排序示例 done

25 运行时间运行时间依赖于输入 ( 输入驱动算法执行 ) 一个已经排好序的序列更容易排序通常情况下, 较短的序列更容易排序, 因此, 我们用输入的大小来参数化运行时间通常, 我们想要获取的是运行时间的上界实际上每个人都更倾向于获得一种保证

26 算法的时间复杂性最坏情况下的时间复杂性 T max (n) = max{ T(I) size(i)=n } 最好情况下的时间复杂性 T min (n) = min{ T(I) size(i)=n } 平均情况下的时间复杂性 T avg (n) = Σ size(i)=n p(i)t(i) 其中 I 是问题的规模为 n 的实例,p(I) 是实例 I 出现的概率

27 机器独立的算法时间插入排序算法的最坏情况需要多少时间呢? 这通常依赖于我们使用的计算机相对速度 ( 在同一机器上 ) 绝对速度 ( 在不同的机器上 ) BIG IDEA: 忽略机器相关的常数只考察 T(n) 随着 n 的增长渐进复杂性 ( Asymptotic Analysis )

28 算法渐近复杂性 T(n), as n (T(n) - t(n) )/ T(n) 0,as n t(n) 是 T(n) 的渐近性态, 为算法的渐近复杂性在数学上, t(n) 是 T(n) 的渐近表达式, 是 T(n) 略去低阶项后留下的主项, 它比 T(n) 简单

29 渐近性能当 n 足够大时, 一个 Θ(n 2 ) 的算法总是能够打败一个 Θ(n 3 ) 的算法在实际应用中, 我们不能直接忽视渐近慢的算法, 因为, 我们通常需要对工程目标进行仔细的平衡渐近分析为结构化算法的思路提供了一种有用的工具

30 渐近分析的记号在下面的讨论中, 对所有 n,f(n) 0,g(n) 0 (1) 渐近上界记号 O O(g(n)) = { f(n) 存在正常数 c 和 n 0 使得对所有 n n 0 有 :0 f(n) cg(n) } (2) 渐近下界记号固定 (g(n)) = { f(n) 存在正常数 c 和 n 0 使得对所有 n n 0 有 :0 cg(n) f(n) }

31 渐近分析的记号 (3) 非紧上界记号 o o(g(n)) = { f(n) 对于任何正常数 c>0, 存在正数和 n 0 >0 使得对所有 n n 0, 有 :0 f(n)<cg(n) } 等价于 f(n) / g(n) 0,as n (4) 非紧下界记号 (g(n)) = { f(n) 对于任何正常数 c>0, 存在正数和 n 0 >0 使得对所有 n n 0, 有 :0 cg(n) < f(n) } 等价于 f(n) / g(n),as n f(n) (g(n)) g(n) o (f(n))

32 (5) 紧渐近界记号 (g(n)) = { f(n) 存在正常数 c 1, c 2 和 n 0 使得对所有 n n 0 有 :c 1 g(n) f(n) c 2 g(n) } 定理 1: (g(n)) = O (g(n)) (g(n))

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

34 插入排序的复杂性分析最坏情况下 : 输入是反向排序的平均情况下 : 所有的顺序以等概率出现插入排序是一个快速的排序算法吗? 当 n 较小时, 性能还可以接受当 n 较大时, 比较差

35 渐近分析中函数比较 f(n)= O(g(n)) a b f(n)= (g(n)) a b f(n)= (g(n)) a = b f(n)= o(g(n)) a < b f(n)= (g(n)) a > b

36 渐近分析记号的若干性质 (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))

37 (2) 反身性 : f(n)= (f(n)) f(n)= O(f(n)) f(n)= (f(n)) (3) 对称性 : f(n)= (g(n)) g(n)= (f(n))

38 (4) 互对称性 : f(n)= O(g(n)) g(n)= (f(n)) f(n)= o(g(n)) g(n)= (f(n)) (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))

39 规则 O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明 : 对于任意 f 1 (n) O(f(n)), 存在正常数 c 1 和自然数 n 1, 使得对所有 n n 1, 有 f 1 (n) c 1 f(n) 类似地, 对于任意 g 1 (n) O(g(n)), 存在正常数 c 2 和自然数 n 2, 使得对所有 n n 2, 有 g 1 (n) c 2 g(n) 令 c 3 =max{c 1, c 2 }, n 3 =max{n 1, n 2 },h(n)= max{f(n),g(n)} 则对所有的 n n 3, 有 f 1 (n) +g 1 (n) c 1 f(n) + c 2 g(n) c 3 f(n) + c 3 g(n) = c 3 (f(n) + g(n)) c 3 2 max{f(n),g(n)} = 2c 3 h(n) = O(max{f(n),g(n)})

40 算法渐近复杂性分析中常用函数 (1) 单调函数单调递增 :m n f(m) f(n) 单调递减 :m n f(m) f(n) 严格单调递增 :m < n f(m) < f(n) 严格单调递减 :m < n f(m) > f(n) (2) 取整函数 x : 不大于 x 的最大整数 x : 不小于 x 的最小整数

41 取整函数的若干性质 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 为单调递增函数

42 (3) 多项式函数 p(n)= a 0 +a 1 n+a 2 n 2 + +a d n d ; a d >0 p(n) = (n d ) f(n) = O(n k ) f(n) 多项式有界 f(n) = O(1) f(n) c k d p(n) = O(n k ) k d p(n) = (n k ) k > d p(n) = o(n k ) k < d p(n) = (n k )

43 (4) 指数函数对于正整数 m, n 和实数 a>0: a 0 =1 a 1 =a a -1 =1/a (a m ) n = a mn (a m ) n = (a n ) m a m a n = a m+n a>1 a n 为单调递增函数 a>1 lim n n b /a n =0 n b = o(a n )

44 e x = 1 + x + x 2 /2! + x 3 /3! + = Σ i x i /i! e x 1+x x 1 1+x e x 1+x+x 2 e x = 1+x+ (x 2 ), as x 0 lim n (1 + x/n) n = e x

45 (5) 对数函数 log n = log 2 n lg n = log 10 n ln n = log e n log k n = (log n) k log log n = log(log n) for a>0, b>0, c>0,a = b log ba

46 b a ab c c c log log ) ( log a n a b n b log log b a a c c b log log log a a b b log ) (1/ log b a a b log 1 log a c b b c a log log

47 x 1 for x > -1, ln(1 x 1 x x x x x) x ln(1 x) x. b b log n log n for any a > 0, lim lim 0 log b n = o(n a ) n a logn (2 ) n a n x 5 5

48 (6) 阶乘函数 n! 1 n( n 1)! n n 0 0 n! n Stirling s approximation n! 2π n n e n 1 1 n

49 n! n π2 n n e n e, 1 12n 1 α n 1 12n n! o( n n ) n! (2 n ) log( n!) ( nlog n)

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

51 小规模数据

52 中等规模数据

53 用 C++ 描述算法

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

55 (1.3) switch 语句 : switch (expression) { case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; }

56 (2) 迭代语句 (2.1) for 循环 : for (init; condition; inc) statement; (2.2) while 循环 : while (condition) statement; (2.3) do-while 循环 : do{ statement; } while (condition);

57 (3) 跳转语句 (3.1) return 语句 : return expression; (3.2) goto 语句 : goto label; label:

$(4) 函数函数定义 return-type function_name(para-list) { body of$

58 (4) 函数函数定义 return-type function_name(para-list) { body of the function } 例 : int max(int x,int y) { return x>y?x:y; }

59 (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);

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

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

62 (6.3) 运算符 delete 当动态分配的存储空间已不再需要时, 应及时释放所占用的空间用运算符 delete 来释放由 new 分配的空间例 : delete y; delete [ ]x; 分别释放分配给 y 的空间和分配给一维数组 x 的空间

63 (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]; }

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

65 Next 算法复杂度分析方法 Algorithm analysis method

C++ 程序设计告别 OJ2 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ2 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ2 - 参考答案 MASTER 2019 年 5 月 3 日 1 1 TEMPLATE 1 Template 描述使用模板函数求最大值使用如下 main 函数对程序进行测试 int main() { double a, b; cin >> a >> b; cout c >> d; cout