前言:
此时你们对“问题规模和算法的时间复杂度”大约比较看重,咱们都想要分析一些“问题规模和算法的时间复杂度”的相关文章。那么小编同时在网上搜集了一些对于“问题规模和算法的时间复杂度””的相关资讯,希望大家能喜欢,各位老铁们快快来学习一下吧!一、时间复杂度定义它是用来衡量算法随着问题规模增大,算法执行时间增长的快慢是问题规模的函数:T(n)是时间规模函数;时间复杂度主要分析T(n)的数量级T(n)=O(f(n)) f(n)是算法中基本运算的频度 一般我们考虑最坏情况下的时间复杂度
计算方法:取算法时间增长最快的那个函数项,忽略它的系数
二、空间复杂度定义它用来衡量算法随着问题规模增大,算法所需空间的快慢是问题规模的函数:S(n)=O(g(n)) ;算法所需空间的增长率和g(n)的增长率相同
从图中,可以看到:随着问题规模的增大(横坐标),所需时间的增长率(斜率)差别很大。而且,这种差距随着问题规模的增大而显著地增大。
我们关心的就是算法的这个增长规模速度
三、常用的时间复杂度大小关系
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n)
注: log2n更多写成logn从左至右,时间性能依次降低。
四、复杂度如何计算
int sum=0; 执行1次
for ( int i = 0 ; i <= n ; i++){ int i = 0执行1次,i<=n执行n+2次,i++执行n+1次
sum=sum+i; 执行n+1}
1)时间分析:
该算法执行了3n+6个语句。
假设每个语句执行时间一致,均为常数t。则总时间T =(3n+6)*t。
随着问题规模n的增大,总时间的增长率与n的增长率一致,所以复杂度为O(n)。
2)结论:
复杂度是关于增长率的,所以可以直接忽视常数项。一般可以直接关注循环段基本操作语句(示例中的sum=sum+i)的执行次数。五、时间复杂度计算(单个循环体)
直接关注循环体的执行次数,设为k
1)算法:
int sum=0;
for ( int i = 0 ; i <= n ; i++){
sum=sum+i;}
2)解释:
i 为1 执行了1次
i 为2 执行了2次
…..
i为n 执行了n次 此时仍然满足条件
i=n+1时,跳出循环
所以循环体执行次数:k=n+1
故时间复杂度为O(n).
3)算法:
int sum=0;
for ( int i = 1 ; i <= n ; i=2*i){ sum=sum+i;} 4)解释: i 取值:1,2,4,8… 满足条件:2k≤ n K>log2n时, 跳出循环
所以循环体执行次数:[log2n]
故时间复杂度为O(logn).
六、时间复杂度计算(多个循环体)
两个运算规则:乘法规则,加法规则。
1)算法
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
两个循环体是独立的,采用加法规则:
T(n)=T1(n)+T2(n)=max(T1(n),T2(n)) =O(n²)
2)算法
for ( int i = 1 ; i <= n ; i++){
for(int j=1;j<=n; j=2*j){
sum=sum+j;}}
两个循环体是嵌套的,采用乘法规则:
T(n)=T1(n)*T2(n)=O(nlogn)
七、空间复杂度计算
空间复杂度S(n)指算法运行过程中所使用的辅助空间的大小。
记为:S(n)=O(f(n))
辅助空间:除了存储算法本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。算法原地工作是指算法所需的辅助空间是常量,即O(1)。考试中出现O(1),O(n)较多。
标签: #问题规模和算法的时间复杂度