PHP算法
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) 
顶部
收展
底部
[TOC]
目录
查找算法(1)顺序查找
查找算法(2)二分法查找
排序算法(1)插入排序
排序算法(2)选择排序
排序算法(3)冒泡排序
排序算法(4)快速排序
php算法复杂度
相关推荐
PHP基础
PHP函数
PHP设计模式
PHP版本