《算法时间复杂度剖析》由会员分享，可在线阅读，更多相关《算法时间复杂度剖析（18页珍藏版）》请在装配图网上搜索。
1、算法时间复杂度(The Complexity of Algorithms)1算法时间复杂度的数学意义算法时间复杂度的数学意义 从数学上定义，给定算法A，如果存在函数f(n)，当n=k时，f(k)表示算法A在输入规模为k的情况下的运行时间，则称f(n)为算法A的时间复杂度。其中：输入规模是指算法A所接受输入的数据量的多少算法效率分析 对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为此，通常忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。影响程序运行时间的因素机器的速度（假设完
2、全一样）算法的好坏输入数据规模运行时间=执行次数*每次执行所需的时间。由于每次执行所需的时间必须考虑到机器和编译程序的功能，因此通常只考虑执行的次数而已。例如：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数组数组int sum(int arr,int n)int i,total=0;for(i=0;i n;i+)total+=arri;return total;执行次数 1 n+1 n 1_ 2n+35假设两矩阵a,b皆为n*n。void add(int a ,int b ,int c ,in
3、t n)int i,j;for(i=0;in;i+)for(j=0;jn;j+)cij=aij+bij;6 执行次数 1 n+1 n(n+1)n2 _ 2n2+2n+2 void mul(int a ,int b ,int c ,int n)int i,j,k,sum;for(i=0;i n;i+)for(j=0;j n;j+)sum=0;for(k=0;k n;k+)sum=sum+aik*bkj;cij=sum;7执行次数 1 n+1 n(n+1)n2 n2(n+1)n3 n2_ 2n3+4n2+2n+2算法的渐近时间复杂度算法的渐近时间复杂度 很多时候，我们不需要进行如此精确的分析，究其
4、原因：1.在较复杂的算法中，进行精确分析是非常复杂的。2.实际上，大多数时候我们并不关心F(n)的精确度量，而只是关心其量级。Big-O算完执行次数后，通常利用Big-O来表示此算法的运行时间，如O(n)，亦称为该程序的时间复杂度(time complexity)。Big-O取执行次数中最高次方或最大指数部份的项目即可。如：阵列元素相加为2n+3=O(n)矩阵相加为2n2+2n+1=O(n2)矩阵相乘为2n3+4n2+2n+2=O(n3)运用时间复杂度的观念，我们可以判断该程序的执行效率是否良好。91.O(1)：常数时间(constant time)运行时间为常量2.O(logn)：次线性时间
5、(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很大时 1 log n n n log n n2 n3 2n n!优-0)if(n%2=1)ans=(ans*a)%c;n=n/2;a=(a*a)%c;return ans;12int PowerMod
6、(int a,int n,int c)int ans=1;a=a%c;for(int i=0;in;i+)ans=ans*a%c;return ans;O(log2n)O(n)顺序搜索13int search(int data,int target,int n)int i;for(i=0;i n;i+)if(target=datai)return i;return-1;最佳次数：当数据是第一个时，第一次就找到。最差次数：当数据不存在或数据在最后一个时，需要N次。平均次数：O(n)通常比较最差次数最差次数。二分查找int search(int A,int n,int target)int low
7、=0,high=n-1;while(low=high)int mid=(low+high)/2;if(Amid=target)return mid;else if(Amid target)low=mid+1;else high=mid-1;return-1;14O(log2n)void quicksort(int a,int low,int up)if(lowup)int i=low;int j=up;int t=alow;while(i!=j)while(i=t)j-;if(ij)ai+=aj;while(ij&ait)i+;if(ij)aj-=ai;ai=t;quicksort(a,low
8、,i-1);quicksort(a,i+1,up);O(nlog2n)voidselectsort(intd,intn)for(inti=0;in-1;i+)intm=i;for(intj=i+1;jdj)m=j;if(m!=i)intt=di;di=dm;dm=t;16O(n2)全排列void dfs(int k)void dfs(int k)int i;int i;if(k=n+1)if(k=n+1)couta1;couta1;for(i=2;i=n;i+)for(i=2;i=n;i+)cout ai;cout ai;coutendl;coutendl;else else for(i=1;i=n;i+)for(i=1;i=n;i+)if(tagi=false)if(tagi=false)ak=i;ak=i;tagi=true;tagi=true;dfs(k+1);dfs(k+1);tagi=false;tagi=false;17O(n!)假设机器是每秒108次基本运算，1秒钟内，各种复杂度的算法能够解决的问题的最大规模，如下表：18n!2nn3n2nlog2nN
算法时间复杂度剖析
