简介
数据结构和算法是为了解决代码性能以及节省资源的问题,所以就需要一个方法来考量代码执行效率是否超标,是否占用太多存储空间
这个方法就是 复杂度分析,学习数据结构和算法离不开 复杂度分析
算法的复杂度包括:时间复杂度和空间复杂度,两者以时间复杂度相对重要,因为在 Web 开发中,常见的性能优化策略都是以空间换时间,例如缓存系统
#为什么需要分析复杂度? 分析代码的复杂度可以知道,代码执行效率、消耗资源,以便优化,写出更高质量的代码。
掌握了复杂度分析,在编写代码的,会不经意的估算自己写的代码是否“合格”,有一种一眼扫过,尽在掌握之中的感觉,并且不需要额外取付出时间,那么不划算吗?
大 O 表示法
先来看一段代码:
$sum = 0;
for ($i=0; $i < n; ++$i) {
$sum =+ $i;
}
在不同的环境下执行,结果是不同的,所以我们假设每行代码执行时间为:time
那么 2、3 行代码都需要执行一次,就是 2*time
,4、5 行代码循环次数分别是 n
,那么就是 2n*time
,这段代码的执行时间就是:T(n) = (2+2n)\*time
,从这里可以看出来,所有代码执行时间T(n) 与 每行代码执行次数 n 是成正比
大O表示法公式: T(n)=O(f(n))
T(n)
:所有代码执行时间f(n)
:每行代码执行次数的总和O
:表示T(n)
与f(n)
成正比n
:表示数据规模
所以上面的代码使用大 O 表示法来分析就是:T(n) = O(2+2n)
,它不表示具体执行时间,而是表示 代码执行时间随着数据规模增大的变化趋势,也叫 渐进时间复杂度,简称 时间复杂度
既然它是表示一种变化趋势,那么可以将公式中的低阶、系数、常量这三部分定量值忽略,因为它随着时间变化不会产生任何影响,只需要记录一个最大量级即可,那么上面那段代码的复杂度可以这样写:T(n) = O(n)
如何使用大O表示法分析?
有三种实用的方法:
- 只关注循环次数最多的一段代码
- 加法法则:总复杂度等于量级最大的那段代码复杂度
- 乘法法则:嵌套代码复杂度等于嵌套内外代码复杂度的乘积
- 多个数据规模相加
加法法则:总复杂度等于量级最大的那段代码复杂度
例子:
function count(){
# exmple 1
$sum1 = 0;
for ($i=0; $i <= 100; ++$i) {
$sum1 =+ $i;
}
# exmple 2
$sum2 = 0;
for ($i=0; $i < n; ++$i) {
$sum2 =+ $i;
}
# exmple 3
$sum3 = 0;
for ($i=0; $i < n; $i++) {
$sum3 += $i;
for ($j=0; $j < n; $j++) {
$sum3 += $j;
}
}
return $sum1 + $sum2 + $sum3;
}
上面三个循环分别求 $sum1、$sum2、$sum3 的值
第一个循环的次数为常量,所以忽略不分析,第二个循环和第三个循环分别是:O(n)、O(n²),所以这三段代码中,量级最大的是第三个循环,所以作为函数的时间复杂度
乘法法则:嵌套代码复杂度等于嵌套内外代码复杂度的乘积
具体代码:
function call() {
for ($i=0; $i < $n; $i++) {
$ret =+ f($i);
}
function f($n) {
for ($i=0; $i < $n; $i++) {
$sum =+ $i;
}
return $sum;
}
}
上面代码中,循环中嵌套循环,第 3 行代码执行的次数是 n
,但是它同时调用了 f
函数,算上函数内的执行次数 n
,所以时间复杂度是:T(n) = T1(n) * T2(n) = O(n*n) = O(n²)
多个数据规模相加
例如,一个代码段中有两个循环,循环的次数由两个参数决定,这就是两个数据规模,那么我们无法得知它们谁的量级大,所以需要将它们相加之后作为代码段的复杂度
function call($m,$n)
for ($i=0; $i < $m; ++$i) {
$sum_1 = $sum_1 + $i;
}
for ($i=0; $j < $n; ++$j) {
$sum_2 = $sum_2 + $j;
}
return $sum_1 + $sum_2;
}
无法得知 m
、n
谁的量级大,所以记为:O(m+n)
常量的时间复杂度(按数量级递增):
- 常量阶
O(1)
- 对数阶
O(logn)
- 线性阶
O(n)
- 线性对数阶
O(nlogn)
- 平方阶
O(n²)
、立方阶O(n³)
... K次方阶O(n^k)
- 指数阶
O(2^n)
- 阶乘阶
O(n!)
O(1)
代码段中不包含循环语句、递归,那么时间复杂度都是 O(1)
O(logn)、O(nlogn) 最为常见,也是最难分析的一种复杂度。
一个简单的例子:
$i = 1;
while($i <= n){
$i *= 2;
}
每次循环都乘于 2,当大于 n
时就停止循环,这样的增长趋势,变量 i
的取值是一个等比数列,所以这段代码的时间复杂度是:O(log₂n)
上面的的对数底是 2,但是不管底是多少,时间复杂度都记为:O(logn)
对数之间是可以互相转换的,log₃n = log₃2 * log₂n 所以:O(log₃n) = O(C * log₂n) C=log₃2 是一个常量,忽略之后就成了:O(Cf(n)) = O(f(n)) 所以不管底是多少都统一记为:
O(logn)
如果一段代码的时间复杂度是 O(logn)
,我们循环执行 n
遍,时间复杂度就是 O(nlogn)
了,比如,归并排序、快速排序的时间复杂度都是 O(nlogn)
。
#空间复杂度分析 表示算法的存储空间与数据规模之间的增长关系,全称:渐进空间复杂度
function call() {
$var = 1;
$arr = [$n];
}
代码第二行申请了一个大小为 1 的空间存储变 var
,因为是常量所以忽略。
第三行申请了一个大小为 n
的空间存储变量,所以整个代码段空间复杂度为:O(n)
常量的空间复杂度:
O(1)
O(n)
O(n²)
相关工具
Q.E.D.
Comments | 0 条评论