浅析算法设计与算法时间复杂度

龙源期刊网浅析算法设计与算法时间复杂度作者：刘军来源：《电脑知识与技术·学术交流》2008年第14期摘要：算法设计与算法时间复杂度分析是数据结构中研究算法的重要内容。本文主要介绍如何针对实际问题设计效率较高的算法以及对算法的时间复杂度进行分析的方法。关键词：算法；算法设计；时间复杂度中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)14-20878-031算法的定义与特性算法是一个有穷的指令集，这些指令是为解决某一特定任务规定了一个运算序列。一般应具有如下特性：(1)输入：应有0个或多个输入；(2)输出：有一个或多个结果输出；(3)确定性：每一步定义都是确切的、无歧义的；(4)有穷性：算法应在执行有穷步后结束；5)有效性：每一条运算应足够基本。2算法的描述算法的描述方法一般有：语言方式、图形方式、表格方式等。算法的描述原则：自顶向下、逐步求精的结构化程序设计方法。下面以直接选择排序说明算法描述过程。选择排序的基本思想是：每一趟（例如第i趟，i=0,1,…,n-2）在后面n-i个待排序对象中选出关键码最小的对象,作为有序对象序列的第i个对象。待到第n-2趟作完，待排序对象只剩下1个，就不用再选了。基本步骤是：龙源期刊网[i]～a[n-1]中选择具有最小关键码的对象；若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调；在这组对象中剔除这个具有最小关键码的对象，在剩下的对象a[i+1]～a[n-1]中重复执行，直到剩余对象只有一个为止。算法框架：for(inti=0;i＜n-1;i++){//n-1趟从a[i]检查到a[n-1];若最小的整数在a[k],交换a[i]与a[k];}细化程序：voidselectSort(inta[],constintn){//对n个整数a[0],a[1],…,a[n-1],按非递减顺序排序for(inti=0;i＜n-1;i++){intk=i;//从a[i]检查到a[n-1],找最小的整数,在a[k]；for(intj=i+1;j＜n;j++)if(a[j]＜a[k])k=j;//k指示当前找到的最小整数inttemp=a[i];a[i]=a[k];a[k]=temp;//交换a[i]与a[k]}}算法求精，提高效率：voidselectSort(inta[],constintn){//对n个整数a[0],a[1],…,a[n-1],按非递减顺序排序for(inti=0;i＜n-1;i++){intk=i;//从a[i]检查到a[n-1],找最小的整数,在a[k]；for(intj=i+1;j＜n;j++)if(a[j]＜a[k])k=j;//k指示当前找到的最小整数if(k＜＞i)龙源期刊网找到的最小整数不是当前序列中的第一个{inttemp=a[i];a[i]=a[k];a[k]=temp;}//交换a[i]与a[k]}}3算法时间复杂度的大O表示法对于有N个元素的数组，如果每一个元素搜索概率相等，那么搜索第1个元素要做1次比较，搜索第2个元素要做2次比较……，搜索第n个元素要做n次比较，从算法的整体看，搜索成功的平均比较次数为(n＋1)/2，因此找到一个函数f(n)=(n+1)/2，然后使用大O表示法T(n)=f(n)=O(n)来作为这个算法的时间复杂度的渐进度量值。要全面分析一个算法，要考虑算法在最坏情况下、最好情况下的时间代价和在平均情况下的时间代价。对于最坏情况用大O表示法来描述。算法的渐进时间复杂度为T(n)=O(f(n))，算法的渐进时间复杂度随n变化。使用大O表示法要考虑关键操作的程序步数，找出其与n的函数关系g(n),从而得到渐进时间复杂度。设g(n)＝2n3+2n2+2n+1，当n充分大时，T(n)＝O(n3)，因为当n很大时2n2+2n+1可以忽略不计。因此，使用大O表示法时只保留最高次幂的项。当g(n)的数量级是对数级时，可能是log2n取下界或log2n取上界的线性关系，使用大O表示法，只要记为O(log2n)即可。数量级关系取：c＜log2n＜n＜nlog2n＜n2＜n3＜2n＜3n＜n!；大O表示法加法规则：针对并列程序段：T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))；大O表示法乘法规则：针对嵌套程序段：T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))；算法时间复杂度的大O表示法分析实例1：voidexample(floatx[][],intm,intn,intk){floatsum[];for(inti=0;i＜m;i++){//x[][]中各行sum[i]=0.0;//数据累加龙源期刊网(intj=0;j＜n;j++)sum[i]+=x[i][j];}for(i=0;i＜m;i++){//打印各行数据和cout＜＜Line＜＜i＜＜:＜＜sum[i]＜＜endl;}两个并列循环的渐进时间复杂度为O(max(m*n,m))；算法时间复杂度的大O表示法分析实例2：template＜classType＞voiddataList＜Type＞::bubbleSort(){//起泡排序的算法//对表Element[0]到Element[n-1]逐趟进行比较,n是表当前长度inti=1;intexchange=1;//当exchange为0则停止排序while(i＜n&&exchange){BubbleExchange(i,exchange);i++;}//一趟比较}template＜classType＞voiddataList＜Type＞::BubbleExchange(constinti,int&exchange){exchange=0;//假定元素未交换for(intj=ArraySize-1;j＞=i;j--)if(Element[j-1]＞Element[j]){Swap(j-1,j);//发生逆序，交换Element[j-1]与Element[j]；exchange=1;//做“发生了交换”标志}}渐进时间复杂度为＜E:\2008学术交流\2008学术交流第二卷第五期(2008总第14期)\第2次28\3软件设计开发\lj01.tif＞。龙源期刊网参考文献：[1]DE克努特.管纪文译.计算机程序设计技巧3[M].北京:国防工业出版社,1999:185-190.[2]许卓群.数据结构[M].北京:高等教育出版社,1993:103-108.[3]严蔚敏.数据结构[M].北京:清华大学出版社,2004:207-215.