龙空技术网

数据结构的时间和空间复杂度详细总结

一点网 154

前言:

此时你们对“问题规模和算法的时间复杂度”大约比较看重,咱们都想要分析一些“问题规模和算法的时间复杂度”的相关文章。那么小编同时在网上搜集了一些对于“问题规模和算法的时间复杂度””的相关资讯,希望大家能喜欢,各位老铁们快快来学习一下吧!

一、时间复杂度定义它是用来衡量算法随着问题规模增大,算法执行时间增长的快慢是问题规模的函数: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)较多。

标签: #问题规模和算法的时间复杂度