算法设计：第3讲——2013.ppt

直接计算法：循环的次数与问题规模n直接或间接相关。 与问题规模n直接相关 x=0;y=0; for(k=1;k=n;k++) x=x+1; for(i=1;i=n;i++) for(j=1;j=n;j++) y=y+1; 非递归算法的时间复杂度分析方法 统计嵌套层数最多的语句的频度。 循环次数间接依赖规模n x=1; for(i=1;i=n;i++) for(j=1;j=i;j++) for(k=1;k=j;k++) x=x+1; 非递归算法的时间复杂度分析方法 执行次数：[n(n+1)(2n+1)/6+n(n+1)/2]/2 时间复杂度：O(n3) 循环次数间接依赖规模n 相关例题： （1）冒泡排序：内循环线性递减 （2）选手的竞技淘汰比赛：内循环呈n/2k递减（k=1,2,…log2n）——几何级数 （3）洗牌程序：内循环呈n/k递减（k=1,2,…,n)——调合级数 非递归算法的时间复杂度分析总结 直接计算法：使用循环次数已知的情况。 迂回计算法：循环结构中循环次数与循环体内语句的执行有联系。 先设循环次数为k 根据循环结束的条件求出k 计算算法复杂度的阶 迂回计算法 例1：算法 void fun1(int n) { int i=1,s=100; while(in) { k=k+1; i+=2; } } 迂回计算法 例2：算法 void fun2(int n) { int i=0,s=0; while(sn) { i++; s=s+i; } } 迂回计算法 例3：算法 void fun2(int n) { int i=0,j; do { for(j=0;jn;j++) i+=j; } while(in+1); 迂回计算法 选取算法中的一个初等操作作为基本操作，然后估计这个操作在算法中的执行频率。 基本操作的选取：只要算法中某个基本操作的执行频率正比于任何其他操作的最高执行频率，都可以选取为基本操作。 基本操作频率的统计 定义：算法中的某个初等操作，如果它的最高执行频率和所有其他初等操作的最高执行频率，相差在一个常数因子之内，就说这个初等操作是一个基本操作。 基本操作频率的统计 举例：假定A是一个具有n个元素的整数数组，给定3个下标：p,q,r，0≤p≤ q≤ r＜ m ，使得 A[p] ～ A[q]和A[q+1] ～ A[r]分别是两个以递增顺序排序的子数组。把这两个子数组按递增顺序合并在A[p] ～ A[r] 中。 算法设计 基本操作频率的统计 分析该算法中的比较次数： 令数组1的长度为n1，数组2的长度为n2，其中n1+n2=n 在进行排序时，比较的次数 最少：n1次 最多：n-1次 基本操作频率的统计 因此，如果合并两个大小接近的有序数组，例如 这时，可以选取数组元素的比较操作作为算法的基本操作。因为此时数组元素的比较操作，和所有其他初等操作的最高执行频率，相差在一个常数因子之内。这时，算法的时间复杂性仍然是Θ(n)。 基本操作频率的统计 很多问题，都可以选择一个基本操作，通过寻找这个基本操作的阶，而得出算法运行时间的阶。 基本操作的选择，通常 检索和排序：元素比较操作 遍历链表：设置或更新链表指针 图的遍历：访问图中顶点 基本操作频率的统计 在大部分情况下，算法的执行时间不仅与问题的规模有关，而且与输入的实例有关。 根据输入实例的不同，又把算法的时间复杂性分为 最好情况分析 平均情况分析 最坏情况分析 时间复杂度的分析 例：用插入法对n个元素的数组A，按递增顺序进行排序。算法设计 （1）最好情况分析： （2）最坏情况分析： 时间复杂度的分析 进行n-1次比较 最好情况与最坏情况分析 寻找该算法的极端实例，然后分析在该极端实例下算法的运行时间。 例1：线性检索法：在n个元素的数组中，用线性检索方法检索元素x。 例2：二叉检索算法：在具有n个已排序过的元素的数组中，二叉检索方法检索元素x。 时间复杂度的分析 平均情况分析： 算法的运行时间取算法所有可能输入的平均时间。 必须知道所有输入出现的概率，即所有输入的分布情况。 在一般情况下，假定输入是平均分布的（等概率）。 时间复杂度的分析 例1：插入排序算法的平均情况分析。假定数组A中的元素为： 并且： （1）插入排序算法中元素比较次数，取决于数组中元素的初始排列顺序。n个元素共有n!种排列，假定每一种排列的概率相同。 时