关于php:PHP数据结构在学数据结构和算法的时候我们究竟学的是啥

一说到数据结构与算法，大家都会避之不迭。这原本是一门业余基础课，然而大部分人都并没有学好，更不用说我这种科班出身的码农了。说实话，还是很艳羡科班出身的程序员，因为你们在日常工作或者面试中，只须要温习一下就好了，而我则是齐全的从头开始学。不过，还好所有都不晚，在这里，咱们就用 PHP 作为示例代码，来和大家一起真正的从头学一遍恐怖的数据结构与算法。

什么是数据结构呢？

数据结构是带“构造”的数据元素的汇合，“构造”就是指数据元素之间存在的关系

这是严蔚敏老师在《数据结构》第二版中对数据结构的定义。其实，就是对于数据的一种组合模式。就像你去一家书店，或者是图书馆，或者是你家的书柜。这些书应该怎么摆放呢？对于书的摆放模式，就是数据结构。你能够乌七八糟的摆放，也能够分门别类的摆放，也能够依据本人的兴趣爱好摆放，也能够将最罕用的书放在手边，将不常看的书放在柜子的深处。这些都是数据结构。

在程序世界中，数据结构蕴含两种模式，一种是逻辑构造，一种是物理构造。

即便你齐全没有接触过数据结构，但只有你学习过编程，肯定会多多少少地据说过这样一些名词：汇合、线性表、树、图，它们指的就是数据结构中的逻辑构造。也就是从逻辑关系上形容数据，是具体问题形象进去的数学模型。比方咱们将书进行分类，每个分类下放着绝对应的书籍，这就是一种树形构造。或者咱们将书按书名拼音建设索引，而后在书架上贴上索引标签，这就是一种哈希构造。

逻辑构造将是咱们整个学习中的一个重点，因为各种算法都是针对这些构造的操作实现。这个咱们在上面的算法解释中再进行具体的阐明。

物理构造次要是数据的物理存储形式，也叫做存储构造。这个十分好记，它只有两种模式，顺序存储构造和链式存储构造。通常，顺序存储构造咱们应用数组来示意，而链式存储构造在 C 语言中应用构造体的指针来示意，但在 PHP 中，链式构造咱们将应用类来表述。

下面说的那些逻辑构造，都能够用程序或者链式的形式来实现，不论应用哪种形式，都能够实现对应逻辑构造的算法操作，但不同的模式或者算法又有不同的效率。而效率，正是整个数据结构和算法学习外围中的外围。

接下来咱们看看什么是算法。

算法是一个无限指令集，它承受一些输出（有些状况下不须要输出），产生输入，并肯定在无限步骤之后终止

这是陈越老师在浙大版《数据结构》第二版中对于算法的定义。其实咱们简略点了解的话，针对下面的数据结构的一系列操作，就是算法。比如说咱们定义了一个树，如何遍历这颗树呢？这就是一个算法，遍历一颗树有先序、中序、后序，也能够进行层序遍历，有这么多种办法，哪种好？哪种不好？用哪种物理构造？线性还是链式？这些论断都以算法的执行效率为根底。能够说，算法品种繁多，效率也千差万别，然而，不能一棒子打死说某个算法肯定不好，每种算法也有它不同的利用场景。这就是咱们要钻研算法的起因。

对于算法，咱们最关怀的是它的效率，这个效率在这里咱们应用的是工夫复杂度和空间复杂度来定义的。

工夫复杂度个别应用 O(n) 来示意，它关怀的是问题规模和语句频度，个别会以 n 示意问题规模（留神，这个 n 是未知的，如果这个 n 是已知的，那么它就是常数阶）。这个 n 有可能是一个常数（n 明确等于多少），记成 O(1)。这是最好的状况，也能够线性增长，如 O(n)。当然也可能对数或指数级增长，O(logN)、O(N^2)，当然最要不得的是 O(2^N) 级的增长，这种状况下可能有生之年你都看不到运算的后果了。

咱们能够看看简略的一段代码来剖析它的工夫复杂度：


echo $a++, PHP_EOL; // O(1)

$n = 10; // 假如一个数量用于测试，理论这个 n 是未知的，如果面试题代码中真的呈现了这种已知 n 的状况，那么这个算法就是 O(1)
for($i = 0;$i<$n;$i++){echo $i, PHP_EOL;}
// O(n)

for($i = 0;$i<$n;$i*=2){echo $i, PHP_EOL;}
// O(logN)

for($i = 0;$i<$n;$i++){for($j = 0;$j<$n;$j++){echo $i, $j, PHP_EOL;}
}
// O(N^2)

从下面代码中能够看出，循环嵌套次数与 n 的增长有很大的关系，另外就是看在循环外部的操作也会影响到增长的状况。比方如果咱们是这样一段代码：

$n = 10; // 假如一个数量，理论这个 n 是未知的
$m = 3; // 假如一个数量，理论这个 m 是未知的
for($i = 0;$i<$n;$i++){for($j = 0;$j<$m;$j++){echo $i, $j, PHP_EOL;}
}

那么它的工夫复杂度就不是 O(N^2) 而是，O(NM)，因为咱们这两层循环并不是都是对最大的 N 的操作，而是 N * M 的操作。然而，如果当 M 很大甚至等于 N 的时候，那么这个算法也就成为了 N^2。

对于工夫复杂度的剖析其实是须要一些数学功底的，然而对于我这种半吊子出身的码农来说，把握住循环档次以及循环内的操作状况就能够大抵地剖析出一段算法的工夫复杂度了。当然，对于某些大厂比拟刁钻的面试题来说，还是须要用数学方法进行合成求得正确的工夫复杂度。

另外，在一段算法或者说一个函数中，工夫复杂度以最大的那个为准，同时，也要思考最好和最差工夫复杂度，因为基于数据规模有可能在数据量大的时候工夫复杂度会越来越惨。这个时候咱们就会以最差工夫复杂度来作为这一段算法的最终工夫复杂度。

对于工夫复杂度的问题，能够参考各类算法书籍，当然最好是以大学教材及练习题为主，多做题就能把握得更深刻。

绝对工夫复杂度来，空间复杂度在数据结构和算法中要关怀的少一些，因为大部分状况下咱们只借助一个第三方变量的话，这个空间复杂度就是 O(1)。而如果须要借助一个数组或者链表来实现算法的话，这个算法的空间复杂度就是 O(n)。

个别状况下咱们不太会去过于的关注空间复杂度，因为大部分算法根本都会维持在 O(1) 或 O(n) 这个级别。当然，也就一些算法会呈现占用十分大的空间复杂度的状况，这样分分钟就能撑爆你的内存。当在遇到这类算法的时候，咱们会独自来阐明空间复杂度的状况。

第一篇文章都是以实践方面的货色为根底的，这也是学习数据结构与算法的理论状况，必须是实践与理论相结合的学习。让咱们从此开始，迈向这个深不见底的超级大坑吧！！

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

===========

各自媒体平台均可搜寻【硬核项目经理】

数据结构

逻辑构造

物理构造

算法

工夫复杂度

空间复杂度

总结