数据结构:时间复杂度和空间复杂度求解思路方法详解-创新互联
- (一)时间复杂度和空间复杂度的作用?
- (二)时间复杂度和空间复杂度如何计算?
- (1)时间复杂度
- 具体案例分析
- 时间复杂度的比较
- (2)空间复杂度
- 两种常见空间复杂度
答:度量算法的效率
- 时间复杂度:用来衡量执行算法所花费的时间;
- 空间复杂度:用来衡量执行算法所占用的空间;
频度:一个语句的频度是指该语句在算法中被执行的次数。
时间复杂度,即分析算法中所有语句的频度之和T(n)的数量级。
因为算法中最深层循环内的语句的频度与T(n)同量级,因此通常采用算法中最深层循环内语句的频度f(n)来分析算法的时间复杂度。将其记作:
T
(
n
)
=
O
(
f
(
n
)
)
T(n)=O(f(n))
T(n)=O(f(n))
注意: 在实际计算中,一般取f(n)中随n增长最快的项,将其系数置为1作为时间复杂度的度量。
例如:f(n)=an³+bn²+cn 的时间复杂度为 O(n³);f(n)=5 的时间复杂度为O(1)
- 类型一:
void func(n){int i,j;
for(i=0;ifor(j=i;j printf("每天进步一点点");
}
}
}
分析:
① 找最深层循环内的语句的频度,即printf("每天进步一点点");
的执行次数;
- 当 i=0 时—— j 对应深层循环执行 n 次
- 当 i=1 时—— j 对应深层循环执行 n-1 次
- …
- 当 i=n-1 时—— j 对应深层循环执行 1 次
- 则最深层循环语句执行次数为: n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1)
② 取f(n)中随n增长最快的项,将其系数置1,即该函数的时间复杂度为 O(n²) 。
- 类型二:
void func(n){int i;
for(i=1;iprintf("每天进步一点点");
}
}
分析:
① 找最深层循环内的语句的频度,即printf("每天进步一点点");
的执行次数;
- 当循环内语句执行次数为 1 时—— i=1
- 当循环内语句执行次数为 2 时—— i=2
- 当循环内语句执行次数为 3 时—— i=2²
- …
- 当循环内语句执行次数为 k 时—— i= 2 k − 1 2^{k-1} 2k−1
- 则如果当 i=
2
k
2^{k}
2k 时不满足条件 i
② 取f(n)中随n增长最快的项,将其系数置1,即该函数的时间复杂度为 O( l o g 2 n log_2n log2n) 。
时间复杂度的比较O(1)常数阶< O(logn)对数阶< O(n)线性阶< O(n²)平方阶< O(n³)(立方阶)< O( 2 n 2^n 2n) (指数阶)
(2)空间复杂度一个程序在执行时所需空间包括:存储本身所用的指令、常数、变量和输入数据的空间,以及对数据进行操作处理所申请使用的辅助空间等。
空间复杂度,使用S(n)来定义算法所耗费的存储空间,记作 S ( n ) = O ( g ( n ) ) S(n)=O(g(n)) S(n)=O(g(n))
两种常见空间复杂度- 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)。例如:
void func(n){int i=1;
int j=2;
int k=i+j;//算法空间与n无关
}
- 如果随着输入值 n 的增大,程序申请的临时空间也随之变化,则程序的空间复杂度需要具体分析,例如:
void func(n){int a[n];//所申请的空间随着n的取值而进行线性变化,空间复杂度为O(n)
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:数据结构:时间复杂度和空间复杂度求解思路方法详解-创新互联
本文链接:http://myzitong.com/article/dgjdgp.html