算法与数据结构学习笔记

Posted on | Edited on | In

算法与数据结构简单介绍

什么是数据结构与算法？ 根据我的理解，数据结构就是指一组数据的存储结构，而算法就是操作这些数据的方法。数据结构与算法是相辅相成的，数据结构是为算法服务的，而算法也是作用在特定的数据结构之上的。

为什么要学习数据结构与算法

可以写出性能更好的代码

大佬们都说算法是一个程序员的内功，一个好的程序 = 数据结构 + 算法，学好算法与数据结构可以使你的程序性能更好，写出更优的程序，可以解决更快、更省的处理、存储数据。

拓展自己的思维

算法实际上就是一种解题的思路与方法，可以帮助自己能更好的理解一些大佬们的项目源码。现在有很多成型的框架，只停留在用的阶段如简单的CURD，用的时候也没有太考虑性能的问题，也不清楚底层的设计原理。虽说工作中大部分用不到，拓展下思维也是不错的。

做一个有追求的码农

平时工作上CURD的工作比较多，很多深层次的东西也都没有接触过，原理、设计模式也懂得不多，几乎是面向领导编程。所以想多练练基本功，就好比房子也得把地基打好，本人作为一名很渣的PHPer，学习一下算法，然后顺便做下笔记，希望做一个有追求的码农吧~~

复杂度分析

什么才是好的算法呢，举个例子，A同学与B同学分别处理一个相同的需求，A同学写的代码执行时间是100ms,占用内存10M，而B同学写的代码执行时间是10s，占用内存为100M。那么就可以认为A同学的程序算法比B同学的更优。一般情况下，我们以运行时间及占用内存两个指标还衡量一个算法的好坏。

事后统计法

事后统计法大概的意思就是先把代码跑一遍，然后再去统计这个算法代码用的时长以及它所占用的内存大小，这种方法存在一定的问题。

事后统计法弊端

1.与环境相关

在不同的测试环境中对测试的结果差异可能会很大，举个例子，我们用同一段代码分别在超级计算机与普通计算机上运行，运行的速度肯定是超级计算比较快。

2.与数据规模相关

当你在使用同一个算法时，不同的数据规模的执行效率可能是平方阶的增加，在相同的数据规模下，执行的效率也会有很大差别，比如排序算法，如果数据本来就是有序的，算法可能不需要做任何排序操作，执行效率会很快，在同等的数据规模下数据是完全倒序的，那么执行效率差别会比较大。所以在数据规模比较小或者数据不确定的情况下，使用事后统计法无法真实的反应出算法的性能。

渐近复杂度

事后统计法存在很大的弊端，那么我们就应该事先对程序进行粗略的性能分析，这就是复杂度分析，也叫渐进复杂度，其中又包括渐近时间复杂度(时间复杂度)跟渐近空间复杂度(空间复杂度)，主要的作用是来分析算法执行效率与数据规模之间的增长关系。

时间复杂度

算法的时间复杂度是一个函数，描述算法的运行时间，使用大O符号表示。这样描述还是有点难懂的，我们用下面的代码来分析一下。

大O表示法
1
2
3
4
5
6
7
8
9
<?php
    //计算1+2+3+....+n的和
    function calc($n) {
        $sum = 0;
        for ($i = 1; $i <= $n; $i++) {
            $sum += $i;
        }
        return $sum;
    }

以上的代码声明了一个函数，函数的作用是计算1+2+3+....+n的和，我们现在估算一下这段代码需要执行的时间。我们假设每行代码的执行效率是一样的，需要一个time时间。那么第4行代码执行一次需要1个time的执行时间，第5、6行都执行了n遍，那么就是2n*time个执行时间，那么这段代码总的执行时间就为(2n+1)*time。可以看出代码执行时间T(n)与每行代码执行次数成正比。

由此我们可以总结出一个公式

1
T(n) = O(f(n))

T(n)代表代码所执行的时间，n代表数据的规模，f(n)代表每行代码所执行的次数总和。公式中的O表示代码执行时间T(n)与f(n)表达式成正比。所以第一个例子我们可以得出T(n) = O(2n+1)，这就是大O表示法，它实际并不代表代码真正的执行时间，它主要是来粗略的分析算法执行效率，表示代码执行时间与数据规模的增长关系。

忽略表达式的某些部分

我们在计算时间复杂度的时候是否真的要一行一行的去计算，如果有好几千行的代码也要一行一行的去计算么，答案显然不是的，那我们是否可以忽略掉表达式的某些部分，所以我们一般计算大O的时间复杂度，会忽略掉公式中的常量、低阶、系数，只考虑阶数高的那一部分。所以一般在分析代码的复杂度时，只关注循环执行次数最多的那一段代码就可以了。还是举个例子，如下

1
2
3
4
# 以下是时间开销与数据规模n的关系
  1. T(n) = O(2n + 1)
  2. T(n) = O(n^2 + 2n)
  3. T(n) = O(n^3 + n^2 + 3n)

我们认为当数据规模n足够大的时候，我们可以忽略更低阶的部分表达式(抓大放小)

1
2
3
4
若n = 2000时，则
2n + 1 = 4001                      VS           2n = 4000
n^2 + 2n = 4004000                 VS           n^2 = 4000000
n^3 + n^2 + 3n = 8004006000        VS           n^3 = 8000000000

由上可得按比例来算，相差结果并不大，我们会将常量、低阶、系数进行忽略，只取阶数高的部分，其实2n我们还可以将2进行忽略把它的时间复杂度变成O(n)。总结的话就是总的时间复杂度等于阶数最高的那一部分代码，总结成公式的话就是以下，称为加法规则。

下面代表如果T1(n) = O(f(n)), T2(n) = O(g(n))，可以转换成下面这样。

1
2
多项相加，只保留最高阶的项，且系数变为1
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

除了加法规则还有乘法规则，如果T1(n) = O(f(n))，T2(n) = O(g(n))，那么它总的时间复杂度就是以下

1
2
多项相乘都保留
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))

比如下面嵌套两层循环的代码，他的复杂度就为O(n^2)，嵌套循环代码的复杂度等于外层与内层的乘积。

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

我们来看下面这段代码，看下他的复杂度是多少

1
2
3
4
5
6
7
8
<?php
    function foo($n) {
        $num = 1;
        while ($num < $n) {
            $num *= 2;
        }
        return $num;
    }

暂时先写到这，后续继续更新。。。。。