算法复杂度科普

发表于   |   分类于   |  

对于算法自己确实很菜，吃了很多亏就不说了，所以最近准备好好补充下相关知识，先拿复杂度分析来说吧。惯用三联 是什么？ 为什么？ 如何学习与改进？

什么是复杂度分析

数据结构和算法本身就是为了解决 『运行效率』 和 『占用空间』 这个问题的。 如何让程序代码运行的更快，更节省存储空间，这就需要算法了，而执行效率是考核质量的一个很重要的标准。

一般说到算法，我们都会用一个复杂度来说明这个算法的 好与坏 其实这个好与坏就是 优秀算法 和 垃圾算法 的区别了。那么怎么区别呢？这就引出了一个概念 复杂度分析 。

因为涉及到『运行效率』 和 『占用空间』，所以有2个复杂度分析 分别是 时间复杂度分析 和 空间复杂度分析

为什么需要复杂度分析

一般我们会通过 执行一遍代码，通过统计和监控等手段来得到运行的时间和占用内存空间，这种评估算法的执行效率的方法是正确的，一般叫做 事后统计法。但是对于算法我们没有必要都去执行一遍得到一个十分准确的值，而且这种方式会有很多的限制。

1.测试结果依赖测试环境

测试环境硬件的不同会对测试结果产生影响。比如你在一个 I9 的处理器上 和 I3 处理器同时跑想同的代码执行的时间会不一样，毕竟I9处理器的处理速度快了很多

2.测试结果受测试规模的影响

对于同一个算法，数据的有序度和数据量大小都会产生影响

所以我们需要一个可以粗略的统计出算法的分析，也就是复杂度分析。

1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本

时间复杂度分析

大 O 表示法

执行效率粗略的讲就是算法的执行时间。看一段代码

1
2
3
4
5
6
7
8
9
10
function cal($n)
{
    $sum = 0;
    for($i = 1; $i < $n; $i++) {
        $sum += $i;
    }
    return $sum;
}

假设每一行的代码执行效率都是一样的 需要执行的时间是 unit_time, 第一行声明了 $sum 需要一个 unit_time,然后来到循环需要执行 $n 次循环 也就是 n 个 unit_time 所以最终的执行时间是 T(n) = ($n + 1) * unit_time。 可以看出 所有代码的执行时间与每行代码的执行次数成正比。所以可以写作 T(n) = O(f(n))

这就是大O时间复杂度表示法
算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
它表示的不是真正的执行时间，而是代码执行时间随着数据规则的增长而变化的趋势，也叫做『渐进时间复杂度』 简称 『时间复杂度』

时间复杂度分析

因为时间复杂度是表示的一种变化趋势，所以可以忽略掉公式中的低阶、常亮、系数 这些并不会影响增长趋势，只需要记录一个 最大量级 就可以了。

如何观察一段代码的变化趋势用大O表示呢？

1.看循环次数最多的一段代码 比如单循环
2.取量级最大的那段代码次数 比如嵌套循环
3.嵌套代码求乘积 比如递归 多重循环
4.多个规模的求加法 比如方法有2个参数控制循环次数的 这种就是取2者复杂度相加

复杂度量级

随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。复杂度的量级可以粗略的分为两类 多项式量级 和 非多项式量级
常用的多项式量级： O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
非多项式量级：O(2^n)（指数阶）、O(n!)（阶乘阶）

O(1)复杂度

O(1) 这种代码是执行时间不会随着 n 的增大而改变，这样的代码复杂度统统记作 O(1)。一般情况下，只要算法中不存在循环语句、递归等 即使代码有成千上万行他的复杂度也是 O(1)

O(logn) 和 O(nlogn) 复杂度

这种代码其实就是一个等比数列。比如代码

1
2
3
4
5
6
7
8
function cal($n)
{
    $i = 1;
    while ($i <= $n) {
        $i = $i * 2;
    }
}

也就是他每次的 i 都是乘 2，所以就变成了2的x次方等于n的问题，也就是 x=log2n 所以他的时间复杂度就是 O(log2n)。而实际上不管第数是2还是3还是10都是一样的统一记作O(logn)

而当循环执行了上面n次后就变成了 O(nlogn)

O(m+n) 和 O(m*n)

看下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function cal($m, $n)
{
    $sum_1 = 0;
    for ($i = 1; $i < $m; $i++) {
        $sum_1 = $sum_1 + $i;
    }
    $sum_2 = 0;
    for ($j = 1; $j < $n; $j++) {
        $sum_2 = $sum_2 + $j;
    }
    return $sum_1 + $sum_2;
}

这种一般都是由2个参数来决定的规模，而我们并不能评估m和n的规模大小所以就表示成了 O(m+n) 乘法的同理

空间复杂度分析

空间复杂度其实和时间复杂度相似，它表示的是算法的 存储空间与数据规模之间的增加关系 也叫做 渐进空间复杂度 简称空间复杂度

如代码

1
2
3
4
5
6
7
function cal($n)
{
    $a = [];
    for ($i = 0; $i < $n; $i++) {
        $a[$i] = $i * $i;
    }   
}

可以看到声明了一个数组 每次循环给数组添加元素，所以内存会变化的就是数组哪里了，也就是数组循环了几次就会有多少个元素 它的空间复杂度记作 O(n)。
而空间复杂度比时间复杂度要简单一些 常用的 O(1), O(n), O(n^2)

-------------The End-------------