如何计算一个算法的时间复杂度和空间复杂度?
算法的复杂性 算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的资源越低,则该算法的复杂性越低。
计算机的资源,最重要的是时间和空间(即存储器)资源。
因而,算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻,对于任意给定的问题,设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标;另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是我们在选用算法适应遵循的一个重要准则。
因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之,在算法学习过程中,我们必须首先学会对算法的分析,以确定或判断算法的优劣。
1.时间复杂性:例1:设一程序段如下(为讨论方便,每行前加一行号)(1) for i:=1 to n do(2) for j:=1 to n do(3) x:=x+1 ...... 试问在程序运行中各步执行的次数各为多少? 解答:行号 次数(频度)(1) n+1(2) n*(n+1)(3) n*n 可见,这段程序总的执行次数是:f(n)=2n2+2n+1。
在这里,n可以表示问题的规模,当n趋向无穷大时,如果 f(n)的值很小,则算法优。
作为初学者,我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性,如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。
2.空间复杂性:例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:算法1:for i:=1 to n do b[i]:=a[n-i+1]; for i:=1 to n do a[i]:=b[i];算法2:for i:=1 to n div 2 do begin t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t end;算法1的时间复杂度为2n,空间复杂度为2n算法2的时间复杂度为3*n/2,空间复杂度为n+1显然算法2比算法1优,这两种算法的空间复杂度可粗略地表示为S(n)=O(n)信息学比赛中,经常是:只要不超过内存,尽可能用空间换时间。
...
时间复杂度的数量级如何求得一个算法的时间复杂度为(3n^3+2n
1.快速排序-时空复杂度:快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。
而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。
在实际应用中,快速排序的平均时间复杂度为O(nlogn)。
快速排序在对序列的操作过程中只需花费常数级的空间。
空间复杂度S(1)。
但需要注意递归栈上需要花费最少logn最多n的空间。
2.快速排序-随机化算法:快速排序的实现需要消耗递归栈的空间,而大多数情况下都会通过使用系统递归栈来完成递归求解。
在元素数量较大时,对系统栈的频繁存取会影响到排序的效率。
一种常见的办法是设置一个阈值,在每次递归求解中,如果元素总数不足这个阈值,则放弃快速排序,调用一个简单的排序过程完成该子序列的排序。
这样的方法减少了对系统递归栈的频繁存取,节省了时间的消费。
一般的经验表明,阈值取一个较小的值,排序算法采用选择、插入等紧凑、简洁的排序。
一个可以参考的具体方案:阈值T=10,排序算法用选择排序。
阈值不要太大,否则省下的存取系统栈的时间,将会被简单排序算法较多的时间花费所抵消。
另一个可以参考的方法,是自行建栈模拟递归过程。
但实际经验表明,收效明显不如设置阈值。
3.快速排序的最坏情况基于每次划分对主元的选择。
基本的快速排序选取第一个元素作为主元。
这样在数组已经有序的情况下,每次划分将得到最坏的结果。
一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。
这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。
实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。
所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。
一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。
” 随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。
对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。
解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。
4.设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
一趟快速排序的算法是: 1)设置两个变量I、J,排序开始的时候:I=0,J=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]; 3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与A[I]交换; 4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与A[J]交换; 5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1。
找到并交换的时候i, j指针位置不变。
另外当i=j这过程一定正好是i+或j+完成的最后另循环结束) 例如:待排序的数组A的值分别是:(初始关键数据:X=49) 注意关键X永远不变,永远是和X进行比较,无论在什么位子,最后的目的就是把X放在中间,小的放前面大的放后面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]: 49 38 65 97 76 13 27 进行第一次交换后: 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找) 进行第二次交换后: 27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时:I=3 ) 进行第三次交换后: 27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后: 27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时:I=4,J=6 ) 此时再执行第三步的时候就发现I=J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示: 初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。
{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。
下面程序段的时间复杂度是
一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n)。
因此,算法的时间复杂度记做:T(n)=O(f(n))。
随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。
时间复杂度的概念: 时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样: a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,b0 =>O(n^3); a,b=0,c0 =>O(n^2)依此类推...