算法设计与分析 李清勇 教授 办公室：第九教学楼北201.

Presentation on theme: "算法设计与分析 李清勇 教授 办公室：第九教学楼北201."— Presentation transcript:

1 算法设计与分析 李清勇 教授 办公室：第九教学楼北201

2 引言 1. 评价指标 2. 交流符号 为什么需要这个概念—算法复杂度？ 最大和连续子数列问题： 算法1 算法2 算法3 算法4
算法 算法2 算法 算法4 2. 交流符号 Boss：针对这个问题你们算法的性能怎么样？ Developer 1：A算法复杂度是？？？ Developer 2：B算法复杂度是？？？

3 算法复杂度 ─ 直观定义 算法复杂度是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为 空间复杂性。
时间复杂度和空间复杂度是只依赖于算法求解的问题规模和算法输入的函数 𝑁、𝐼分别表示算法求解的问题规模和算法输入，则算法的时间复杂度𝑇和空间复杂度𝑆可以分别表示为： 𝑇=𝑇(𝑁,𝐼) 𝑆=𝑆(𝑁,𝐼)

4 问题规模 迷宫问题: 在一个N*N的迷宫中，求解从入口到出口的路径，如果不存在路径则返回0。 问题的规模： N=2 VS N=10000

5 输入实例 迷宫问题: 问题规模N=10000时，算法的输入: 在一个N*N的迷宫中，求解从入口到出口的路径，如果不存在路径则返回0。
输入1：没有路径，且入口即被障碍包围 输入2：没有路径，但是在出口处才判定

6 直观定义的困境 影响算法执行时间的因素： 计算机配置 问题规模 输入实例
时间复杂度不应该是在特定计算机上求解某一个输入实例所需要的运行时间；而应该是一个不依赖于计算机配置、问题规模和输入实例的抽象表示。

7 算法复杂度分析 ─ 指令抽象 T(N, I) 表示特定算法在一台抽象的计算机上运行所需要的时间。
K个元运算，O1, O2, …, Ok, 运行一次所需时间为 t1, t2, …, tk; 统计Oi的调用次数为ei，ei = ei(N, I); 因此，T(N, I) = ∑tiei(N, I)。

8 Swap 算法复杂度分析 ─ 指令抽象 冒泡排序算法（升序排列） 2. 1 图像 如果输入为 [1, 2, 3, 4, 5]，
void sort(int *pValues, int iDim) { for (int i = 0; i < iDim; i++) for (int j = 1; j < iDim – i; j++) if (pValues[j] < pValues[j -1]) int iTemp = pValues[j]; pValues[j] = pValues[j - 1]; pValues[j - 1] = iTemp; } 如果输入为 [1, 2, 3, 4, 5]， 需要0次Swap操作 如果输入为[5, 4, 3, 2, 1]， 需要10次Swap操作 Swap 不可能对规模为N的每一种合法输入都统计Swap，需合理的简化

9 算法复杂度分析 ─ 输入特化 最坏情况下的时间复杂性： 最好情况下的时间复杂性： 平均情况下的时间复杂性：
其中 𝐷 𝑁 是规模为𝑁的合法输入的集合； 𝐼 ∗ 是 𝐷 𝑁 中使𝑇(𝑁,𝐼)达到 𝑇 𝑚𝑎𝑥 (𝑁)的合法输入； 𝐼 是 𝐷 𝑁 中使𝑇(𝑁,𝐼)达到 𝑇 𝑚𝑖𝑛 (𝑁)的合法输入；而𝑃(𝐼)是在算法的应用中出现输入I的概率

10 Swap 时间复杂度表示— 输入特化 冒泡排序算法（升序排列） T(N)的表达式比较复杂，需合理的简化！
T(N) = (N-1) + … + 1 = N(N-1)/2 = 0.5N2 – 0.5N void sort(int *pValues, int n) { for (int i = 0; i < n; i++) for (int j = 1; j < n – i; j++) if (pValues[j] < pValues[j -1]) int iTemp = pValues[j]; pValues[j] = pValues[j - 1]; pValues[j - 1] = iTemp; } Boss：这个算法的复杂度怎么样？ Developer：它的复杂度是0.5N2 – 0.5N Boss：神马？囧 N充分大时，比如𝑁= ， 有0.5 𝑁 2 ≫ 0.5𝑁，以至于0.5N可以忽略不计。 Swap T(N)的表达式比较复杂，需合理的简化！

11 时间复杂度表示—函数简化 例1：𝑇 𝑁 =10 𝑁 2 +100𝑁+10000 𝑇 ′ 𝑁 =10 𝑁 2
对于算法A的复杂性函数𝑇(𝑁)，如果存在𝑇′(𝑁) ，使得当𝑁→∞时有 (𝑇 𝑁 −𝑇′(𝑁)) 𝑇(𝑁)→0 ，那么就称𝑇′(𝑁)为算法A当𝑁→∞的渐近复杂性。 例1：𝑇 𝑁 =10 𝑁 𝑁+10000 𝑇 ′ 𝑁 =10 𝑁 2 例2：𝑇 𝑁 = 2 𝑁 + 𝑖=1 100 𝑖∗ 𝑁 𝑖 𝑇 ′ 𝑁 = 2 𝑁 𝑇′(𝑁)是𝑇(𝑁)略去低阶项所留下的主项，表达简单 如果两个算法的渐近复杂性的阶不相同，那么只要确定出各自的阶就可以判断哪一个算法效率高 阶跟𝑇′(𝑁)中的常数因子没有关系， 𝑇′(𝑁)可进一步简化，省略常数因子

12 时间复杂度记号 时间复杂度的记号包括：O Ω Θ

13 时间复杂度记号O O的定义： 注意： O得到的只是一个充分大的上界，这个上界的阶越低则评估就越精确，结果就越有价值！
设f(N)和g(N)是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f(N) ≤Cg(N)，则称函数f(N)当N充分大时上有界，g(N)是f(N)的一个上界，记为f(N)=O(g(N))，即f(N)的阶不高于g(N)的阶。 Cg(N) f(N) 注意： O得到的只是一个充分大的上界，这个上界的阶越低则评估就越精确，结果就越有价值！ g(N) N0

14 例子1 证明： 给定多项式函数：𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +… + 𝑎 1 𝑛+ 𝑎 0 ,
给定多项式函数：𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +… + 𝑎 1 𝑛+ 𝑎 0 , 试证明 𝑇(𝑛)= O(𝑛^𝑘) 证明： 选择 𝑛 0 =1，C= 𝑎 𝑘 + 𝑎 𝑘−1 +…+ 𝑎 𝑎 0 则需要证明 𝑛≥1,𝑇(𝑛)≤𝐶 𝑛 𝑘 对于任意𝑛, 如果𝑛≥1，则： 𝑪 ∙𝒏 𝒌 = 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘 +…+ 𝑎 1 𝑛 𝑘 + 𝑎 0 𝑛 𝑘 ≥ 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +…+ 𝑎 1 𝑛+ 𝑎 0 ≥ 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +…+ 𝑎 1 𝑛+ 𝑎 0 =𝑻(𝒏)

15 例子2 证明（反证法）： 给定多项式函数：𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 , 试证明 𝑇 𝑛 ≠ O( 𝑛 𝑘−1 )
给定多项式函数：𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 , 试证明 𝑇 𝑛 ≠ O( 𝑛 𝑘−1 ) 证明（反证法）： 假设 𝑇 𝑛 = O( 𝑛 𝑘−1 ) ， 则存在 𝑛 0 和C，对于任意𝑛，当𝑛≥ 𝑛 0 时满足： 𝑇 𝑛 ≤𝐶 𝑛 𝑘−1 ，即 𝑎 𝑘 𝑛 𝑘 ≤𝐶 𝑛 𝑘−1 消除 𝑛 𝑘−1 ，得到 𝑛≤ 𝐶 𝑎 𝑘 ，与条件𝑛≥ 𝑛 0 矛盾！

16 运算法则 根据O的定义，容易证明它有如下运算规则： O(f)+O(g)=O(max(f,g))； 2) O(f)+O(g)=O(f+g)；
4) 如果g(N)=O(f(N))，则O(f)+O(g)=O(f)； 5) O(Cf(N))=O(f(N))，其中C是一个正的常数； 6) f=O(f)。 在课堂推理规则（2）

17 时间复杂度记号O 𝑓 𝑛 =3𝑛+2, 𝑔 𝑛 =𝑛 𝑓 𝑛 =6∗ 2 𝑛 + 𝑛 2 , 𝑔 𝑛 = 2 𝑛
𝑓 𝑛 = 𝑛 16 +3∗ 𝑛 2 , 𝑔 𝑛 = 2 𝑛

18 时间复杂度记号 Ω的定义: 如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))，即f(N)的阶不低于g(N)的阶。 Θ的定义：定义f(N) = Θ(g(N)) 当且仅当 f(N)=O(g(N)) 且f(N)= Ω(g(N))，此时称f(N)与g(N)同阶。 定理1：对于多项式函数 𝑓 𝑁 = 𝑎 𝑚 𝑁 𝑚 + 𝑎 𝑚−1 𝑁 𝑚−1 +⋯+ 𝑎 1 𝑁+ 𝑎 0 ，如果 𝑎 𝑚 >0，则有： 𝑓 𝑁 =𝑂( 𝑁 𝑚 )，𝑓 𝑁 =𝛺( 𝑁 𝑚 )，𝑓 𝑁 =𝛩( 𝑁 𝑚 ) 简单说明即可，它只不过是O的一个补充 10/25

19 时间复杂度类别 按照O(f)函数形式把时间复杂度分为两类： 多项式复杂度算法，形如：O(nc) 指数复杂度算法， 形如:O(cn)
举例说明时间复杂性: n=1024时,单个加法运算 O(logn)和O(n)各自所需要的时间； 画出各个函数的草图 1-n的全排列是一个O(n !)问题 O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)…<O(cn)<O(n!)<O(nn)

20 时间复杂度类别比较

21 非递归算法时间复杂性分析 1 确定关键操作 可以是高级程序设计语言中的赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等操作（一般被看作是基本操作，并约定所用的时间都是一个单位）；也可以是由常数个基本操作构成的程序块。 计算关键操作总的执行步数 一般是数列和的形式。 2 求解其渐进阶，并用O(.)表示 3

22 实例--1 问题描述： 算法描述： 给定数组A（长度为n）和数t，判断数组A中是否包含t？ 时间复杂度：O(𝑁)
bool isExist(float* iArray, int n, float t) { for (int i = 0; i < n; i++){ if (iArray[i] == t) return true; } return false; 时间复杂度：O(𝑁)

23 实例--2 问题描述： 算法描述： 给定数组A和B（长度为n）和数t，判断数组A或者B中是否包含t？ 时间复杂度：O(𝑁)
bool isExist(float* iArrayA, float* iArrayB, int n, float t) { for (int i = 0; i < n; i++){ if (iArrayA[i] == t) return true; } if (iArrayB[i] == t) return false; 时间复杂度：O(𝑁) 想想与例1的区别哦！！

24 实例--3 问题描述： 算法描述： 给定数组A和B（长度为n），判断数组A和B中是否包含相同元素？ 时间复杂度：𝑂(𝑁²)
bool isCommon(float* iArrayA, float* iArrayB, int n) { for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) if (iArrayA[i] == iArrayB[j]) return true; } return false; 时间复杂度：𝑂(𝑁²)

25 实例--4 问题描述： 算法描述： 给定数组A（长度为n），判断数组A中是否包含重复元素？ 时间复杂度：𝑂(𝑁²) 想想与例3的区别哦！！
bool isDuplicate(float* iArrayA, int n) { for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++) if (iArrayA[i] == iArrayA[j]) return true; } return false; 想想与例3的区别哦！！ 时间复杂度：𝑂(𝑁²)

26 实例--5 问题描述： 给定升序排列的整数数组A（长度为n）和整数x，判断数组A中是否包含元素x，如果存在则返回其位置，否则返回-1？ 算法描述： int BinarySearch(int* iArrayA, int n, int x) { int left=0; int right=n-1; while(left<=right) int middle=(left+right)/2; if(x== iArrayA[middle]) return middle; if(x> iArrayA[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到x 时间复杂度：O(log⁡(𝑁))

27 递归算法时间复杂性分析 1 分析递归程序的结构，确定每一逻辑块的时间复杂性 非递归的程序块（或者子函数）用非递归方法分析其复杂性；递归函数的复杂性则跟据其输入规模递归地表示。 构造复杂性函数的递推方程 2 3 求解递归方程和渐进阶，并用O(.)表示

28 实例--1 问题描述： 算法描述： 求整数n的阶乘。 时间复杂度：O(𝑁) long FN( long n ) { if (n<=1)
return 1; return n * FN(n-1); } 时间复杂度：O(𝑁)

29 实例--2 问题描述： 算法描述： 时间复杂度：O( 2 𝑁 )
三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 A B C 算法描述： int Hanoi( int n, int a, int b, int c) { if (n<=0) return 0; Hanoi( n-1, a, c, b ); Move( a, c ); Hanoi( n-1, b, a, c ); return 1; } 时间复杂度：O( 2 𝑁 )

30 内存算法 外存算法 编外 在大数据情景下，算法可能需要处理的数据规模是TB级别或者以上，无 法在内存中存储和处理所有数据；
数据 I/O将占用大部分的时间，内存是随机存储，外存是顺序存储。 在内存中取数据类似于在身边桌子上拿一个东西；在外存中取数据类似于坐飞机去美国的某个桌子上取数据。机械手臂先把磁头移动到相应磁道，然后主轴旋转把相应磁区转到磁头下面进行读取。

31 编外 内存算法 外存算法 分布式算法 在分布式情景下，通信模块 将占用大部分的时间

32 作业 试证明 2 𝑁+10 =𝑂 2 𝑁 。 试证明 2 10𝑁 ≠𝑂 2 𝑁 。 给定正函数𝑓 𝑁 ，𝑔(𝑁)，试证明 max 𝑓,𝑔 =𝑂(𝑓 𝑁 +𝑔(𝑁))。

33 谢谢 THANKS