算法

描述

算法就是针对特定问题的求解步骤的一种描述。它是抽象的，不依赖任何一种语言（可以任意使用自然语言、C、C++、流程图等等来表述）。

4个特性

①有穷性：一定是可以在执行一定次数后终止的，不可能永远不能停止。
②确定性：每条语句都有确定的含义，不能有歧义。
③可行性：算法在当前环境条件下可以通过有限次运算实现。
④输入和输出：有零个或多个输入，有一个或多个输出

好算法的标准

①正确性：能够满足特定问题的求解需求，能够正常运行，没有语法错误，且返回的结果符合预期。
②易读性：代码简介、注释清晰，方便别人阅读，并且利于后期调试和修改。
③健壮性：对于非法数据能够很好的校验并处理，例如年龄不可能小于0
④高效性：指的是算法的运行效率比较高，消耗的时间短。但是这里不是根据实际时间来判断的，因为一台老式计算机和一台超级计算机运行同一个代码，执行时间可能相差很大，所以这里是根据算法的基本运行次数来判断的，这个也被称为时间复杂度。
⑤低存储性：指的是算法在运行过程中，消耗的额外存储空间，额外消耗空间越低，那么算法就相对越好。这就是空间复杂度。而且这里是指的额外存储空间，基本上就是除了输入、输出及程序基本语句运行时占用的空间，都算是额外消耗。

时间复杂度

从上面的介绍可以知道，算法的时间复杂度是使用程序运行的次数来判断的。
就比如数学老师提了一个问题，让我们计算1+2+3+...+100的结果是多少
可能有的同学会这样写

function sum($n) {
  // 定义一个变量来计算和
  $sum=0;
  // 然后循环N次，每次都加上对应的值
  for ($i=1;$i<=$n;$i++) {
    $sum += $i;
  }
  // 最后输出结果
  return $sum;
}
echo sum(100); // 5050

这时候有一个同学发现了一个规律，就是1+2+3+...+100可以拆分成
(1+100)+(2+99)+(3+98)+...+(50+51)
这样总共分为了50组，每组的和是101

// 根据上面的规律得到
// 这里注意是针对于上面问题的解答，所以这里的n是一个偶数
function sum($n) {
  $group = $n / 2; // 两两结合，总共多少组
  $base = $n+1; // 每组的和
  return $group * $base; // 返回结果，50 * 101
}

echo sum(100);

可以对比上面两个算法，算法一循环了100次才得到结果，算法二确是只执行了一次就得到了同样的答案。所以算法二相对算法一的时间复杂度就低。

如何时间复杂度呢？

比如这个算法的时间复杂度是如何表示的？

$sum = 0; // 运行1次
$total = 0; // 运行1次

for ($i=1; $i<=$n; $i++) { // 运行 n+1次，最后一次是判断 $i == $n 并且结束循环了。
  $sum += $i; // 运行 n 次

  for ($j=1; $j<=$n; $j++) { // 运行 n * (n+1) 次
    $total += $j;     // 运行 n * n 次
  }
}

把上面所有的次数加载一起就是1+1+(n+1)+n+n*(n+1)+n*n
那么可以表示为T(n)=2n2+3n+3
当n足够大的情况下，基本上次数就取决于2n2了。
计算机科学家们引入了O大写的字母o来表示复杂度，上面的这个算法的复杂度用大O表示就是O(n2)
为什么是n2而不是2n2+3n+3呢？请看大O记法
另外不是每个算法都能直接计算次数的，比如下面这个算法，具体的次数取决于要查询的值在数组中的位置。

function search($arr, $item) {
  for ($i=0;$i<count($arr); $i++) {
    if ($arr[$i] == $item) {
      return $i; // 返回下标
    }
  }
  return -1;
}

最好的情况一次就可以查出来，最坏的情况查到最后才查出来或者压根不在数组里。如果分布概率均等，那么平均情况下(n+1)/2次就可以查询出来。
所以像这种分为最好、最坏、平均情况的算法，一般只用最坏情况作为衡量标准。因为我们能够接受最坏的情况，那么其他情况就更加能接受了。

空间复杂度

输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。

下面分析这个算法的空间复杂度

function swap($x, $y) { // 交换 x 和 y 的值
  $temp = $x; // 创建一个临时变量并存储 x的值
  $x = $y; // 将 y的值赋值给x
  $y = $temp; // 将临时变量赋值给y
}

上面这个算法，使用了一个临时变量，除此之外没有其他的额外消耗，所以它的空间复杂度就是O(1)

大O记法

这就是大O记法的几个特性：

• 忽略常数：比如这里的+3就是一个常数，2也是一个常数，所以在n足够大的情况下，常数的影响是可以忽略的。
• 只保留最高阶：比如这里有n2 和n，同样在n足够大的情况下，还是以n2影响最大