26算法时间复杂度剖析

算法时间复杂度(TheComplexityofAlgorithms)1算法时间复杂度的数学意义从数学上定义，给定算法A，如果存在函数f(n)，当n=k时，f(k)表示算法A在输入规模为k的情况下的运行时间，则称f(n)为算法A的时间复杂度。其中：输入规模是指算法A所接受输入的数据量的多少算法效率分析对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为此，通常忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。•影响程序运行时间的因素•机器的速度（假设完全一样）•算法的好坏•输入数据规模程序运行时间•运行时间=执行次数*每次执行所需的时间。•由于每次执行所需的时间必须考虑到机器和编译程序的功能，因此通常只考虑执行的次数而已。•例如：x=x+1;for(i=1;i=n;i++)for(i=1;i=n;i++)x=x+1;for(j=1;j=n;j++)x=x+1;1次n次n2次4数组intsum(intarr[],intn){inti,total=0;for(i=0;in;i++)total+=arr[i];returntotal;}执行次数1n+1n1________2n+35矩阵相加假设两矩阵a,b皆为n*n。voidadd(inta[][],intb[][],intc[][],intn){inti,j;for(i=0;in;i++)for(j=0;jn;j++)c[i][j]=a[i][j]+b[i][j];}6执行次数1n+1n(n+1)n2________2n2+2n+2矩阵相乘voidmul(inta[][],intb[][],intc[][],intn){inti,j,k,sum;for(i=0;in;i++)for(j=0;jn;j++){sum=0;for(k=0;kn;k++)sum=sum+a[i][k]*b[k][j];c[i][j]=sum;}}7执行次数1n+1n(n+1)n2n2(n+1)n3n2___________2n3+4n2+2n+2算法的渐近时间复杂度很多时候，我们不需要进行如此精确的分析，究其原因：1.在较复杂的算法中，进行精确分析是非常复杂的。2.实际上，大多数时候我们并不关心F(n)的精确度量，而只是关心其量级。Big-O•算完执行次数后，通常利用Big-O来表示此算法的运行时间，如O(n)，亦称为该程序的「时间复杂度(timecomplexity)」。•Big-O取执行次数中最高次方或最大指数部份的项目即可。如：–阵列元素相加为2n+3=O(n)–矩阵相加为2n2+2n+1=O(n2)–矩阵相乘为2n3+4n2+2n+2=O(n3)•运用时间复杂度的观念，我们可以判断该程序的执行效率是否良好。9复杂度量级1.O(1)：常数时间(constanttime)运行时间为常量2.O(logn)：次线性时间(sub-linear)二分搜索算法3.O(n)：线性时间(linear)n个数内找最大值4.O(nlogn)快速排序算法5.O(n2)：平方时间(quadratic)选择排序，冒泡排序6.O(n3)：立方时间(cubic)两个n阶矩阵的乘法运算7.O(2n)：指数时间(exponential)n个元素集合的所有子集的算法8.O(n!)：阶乘时间(factorial)N个元素的全排列的算法如果n很大时→1lognnnlognn2n32nn!优---------------------------劣10复杂度之效率11高次幂取模intPowerMod(inta,intn,intc){intans=1;a=a%c;while(n0){if(n%2==1)ans=(ans*a)%c;n=n/2;a=(a*a)%c;}returnans;}12intPowerMod(inta,intn,intc){intans=1;a=a%c;for(inti=0;in;i++){ans=ans*a%c;}returnans;}O(log2n)O(n)顺序搜索212)1(111nnnnknnk13intsearch(intdata[],inttarget,intn){inti;for(i=0;in;i++)if(target==data[i])returni;return-1;}–最佳次数：当数据是第一个时，第一次就找到。–最差次数：当数据不存在或数据在最后一个时，需要N次。–平均次数：–O(n)–通常比较最差次数。二分查找intsearch(intA[],intn,inttarget){intlow=0,high=n-1;while(low=high){intmid=(low+high)/2;if(A[mid]==target)returnmid;elseif(A[mid]target)low=mid+1;elsehigh=mid-1;}return-1;}14O(log2n)快速排序voidquicksort(inta[],intlow,intup){if(lowup){inti=low;intj=up;intt=a[low];while(i!=j){while(ij&&a[j]=t)j--;if(ij)a[i++]=a[j];while(ij&&a[i]t)i++;if(ij)a[j--]=a[i];}a[i]=t;quicksort(a,low,i-1);quicksort(a,i+1,up);}}O(nlog2n)选择排序voidselectsort(intd[],intn){for(inti=0;in-1;i++){intm=i;for(intj=i+1;jn;j++)if(d[m]d[j])m=j;if(m!=i){intt=d[i];d[i]=d[m];d[m]=t;}}}16O(n2)全排列voiddfs(intk){inti;if(k==n+1){couta[1];for(i=2;i=n;i++)cout''a[i];coutendl;}elsefor(i=1;i=n;i++)if(tag[i]==false){a[k]=i;tag[i]=true;dfs(k+1);tag[i]=false;}}17O(n!)•假设机器是每秒108次基本运算，1秒钟内，各种复杂度的算法能够解决的问题的最大规模，如下表：18n!2nn3n2nlog2nN最大规模1126464100004.5*106100000000