php算法复杂度-KeepStudy

php算法复杂度

算法复杂度分为时间复杂度和空间复杂度。
时间复杂度是指执行算法所需要的计算工作量，即语句执行次数。
而空间复杂度是指执行这个算法所需要的内存空间。

- 时间复杂度
执行算法所需的计算工作量。一般来说，计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做T(n)=O(f(n));
常见时间复杂度有:常数阶、线性阶、平方阶、立方阶、对数阶、nlog2n阶、指数阶
效率：O(1) > O(log2n)> o(n)> o(nlog2n) > o(n^2) > o(n^3) > o(2^n) > o(n!) > o(n^n)

- 最坏情况
最坏情况时的运行时间，一种保证。如果没有特别说明，说的时间复杂度即为最坏情况的时间复杂度

#### 时间复杂度计算方式
- 常数阶 O(1)
```php
function test($n){
  echo $n;
  echo $n;
  echo $n;
}
```
不管$n是多少，只运行3次，那么时间复杂度就是O(3),取为O(1)

- 对数阶：O(log2n)
如果a的x次方等于N（a>0，且a不等于1），那么数x叫做以a为底N的对数（logarithm），记作x=logaN。其中，a叫做对数的底数，N叫做真数。 
```php
while($n>=1){
  $n=$n/2;
}
```
n 执行次数
1 1
2 2
3 2
规律：
第一次 第二次 第三次 第四次 第五次
20--------->10---------->5-------->2.5------->1
n n/2 n/2/2 n/2/2/2 n/2/2/...
所有规律:n/(2^m)=1;我们需要算出m, 转换成n=2^m,得出m=log2n,所以时间复杂度为O(logn)或者O(log2n)

- 线性阶 O(n)
举例：计算1+2+3+....+n的和
```php
$sum=0
for($i=1;$i<=$n;$i++){
  $sum+=$i
}
```
可以看到循环了n次，所以时间复杂度就是O(n), 时间复杂度就是程序计算次数

- 平(立)方阶：o(n2)/o(n3)
```php
$sum=0;
for($i=1;$i<=$n;$i++){
  for($j=1;$j<$n;$j++){
    $sum+=$j
  }
}
```
两次循环，里面循环执行了n次，外层循环也执行了n次，所以时间复杂度为O(n^2),立方阶一样

#### 空间复杂度计算方式
算法需要消耗的内存空间。即为S(n)=O(f(n));包括程序代码所占用的空间，输入数据所占用的空间和辅助变量所占用的空间这三个方面。计算和表达方式与时间复杂度类似，一般用复杂度的渐近性来表示

举例：冒泡排序的元素交换，空间复杂度O(1)
冒泡排序就是两两交换，中间设置临时变量存储交换的值，不管要交换的数据多大，临时变量始终为固定数量

冒泡排序:把$arr=[1,3,2,4,6,5]排序出来
    - 原理：两两相邻的数进行比较，如果反序就交换，否则不交换
    - 首先1和3比较，不动 ->1 3 2 4 6 5
    - 再次3和2比较，交换 ->1 2 3 4 6 5
    - 再次3和4比较，不动 ->1 2 3 4 6 5
    - 再次4和6比较，不动 ->1 2 3 4 6 5
    - 再次6和5比较，交换 ->1 2 3 4 5 6
所以时间复杂度为O(n^2),空间复杂度为O(1)

![](/uploads/20230207/2023020712391579494.png)

顶部

PHP算法

目录

相关推荐