数据结构(牛小飞)第2章算法分析.pptVIP

01算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解。另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。02可读性算法设计的原则当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。健壮性算法设计的原则01通常，效率指的是算法执行时间。02存储量指的是算法执行过程中所需的最大存储空间。03两者都与问题的规模有关。高效率与低存储量需求算法设计的原则算法分析：对算法的执行时间和需要的存储空间进行定性分析，以比较算法、改进算法。1时间复杂度：算法的运行时间空间复杂度：算法运行所需的内存数量。2算法分析程序本身所占空间1辅助变量所占空间2输入数据所占空间算法的空间复杂度定义用S(N)表示。包含以下的部分：3空间复杂度分析运行时间的计算分析模型运行时间中的对数算法分析(教材2.3,2.4)3241任何一个算法都是由有限个基本运算（算术运算、逻辑运算和赋值操作）组成。一般的讲，执行时间与问题规模n有关，是n的函数，记作T(n)，T(n)是非负递增函数为了分析方便，将每种运算所需要的时间统一定义为1个时间单位。算法需要的执行时间为所有运算个数之和分析模型-渐进表示法要分析的问题：输入的大小最好情形、平均情形、最坏情形。Tbest(n)，Tworst(n)，Taverage(n)Tbest(n)≤Taverage(n)≤Tworst(n)分析模型-渐进表示法确定算法的主要操作0101020304计算主要操作执行的次数一般的讲，执行次数是输入的函数根据函数的特点，得到函数所属的阶（order）020304渐进时间复杂性分析方法：分析模型-渐进表示法{++x;s=0;}语句频度为1，T(n)=O(1)for(i=1;i=n;++i){++x;s+=x;}语句频度为n，T(n)=O(n)for(j=1;j=n;++j)for(k=1;k=n;++k){++x;s+=x;}语句频度为n2，T(n)=O(n2)选择排序voidselect_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列。}//select_sort基本操作:比较(数据元素)操作时间复杂度:O(n2)j=i;//选择第i个最小元素for(k=i+1;kn;++k)if(a[k]a[j])j=k;for(i=0;in-1;++i){if(j!=i)a[j]←→a[i]}?常见函数的时间复杂度按数量递增排列及增长率。常数阶O(1)对数阶O(logn)对数平方O(log2n)线性阶O(n)线性对数阶O(nlogn)平方阶O(n2)立方阶O(n3)……k次方阶O(nk)指数阶O(2n)分析模型-渐进表示法如果存在正常数c和n0，当Nn0，T(N)≤cf(N)，则记为T(N)=O(f(N))。O表示法的定义：T1(n)=3n+1≤3n+n≤4nc=4，n0=1T1(n)=O(n),T1(n)=3n+1T(N)不快于f(N)的增长速度分析模型-渐进表示法T2(n)=O(log2(n))c=8,n0=216T2(n) =7log2(n-1)+16 ≤7log2(n)+16 ≤7log2(n)+log2(n)n≥216 ≤8log2(n)如果存在正常数c和n0，当Nn0，T(N)≤cf(N)，则记为T(N)=O(f(N))。O表示法的定义：T(N)不快于f(N)的增长速度因此从渐进的意义上来说，g(n)是f(n)的下界。02f(n)=Ω(g(n))的表示意味着f(n)渐进大于或等于g(n)，01Ω表示法分析模型-渐进表示法T(N)≥cg(N)，则记为T(N)=Ω(g(N))。T1(n)=Ω(n)T2(n)=Ω(log2n)T1(n)=3n+1T2(n) =5log2(n)+7如果存在正常数c和n0，当Nn0，01T(N)不慢于g(N)的增长速度Ω表示法的定义：02分析模型-渐进表示法分析模型-渐进表示法