说到数据结构和算法，大家都会避而远之。这本是一门专业的基础课，但是大部分人都没有学好，更何况是我这种半路出家的码农。说实话，我还是很羡慕有专业背景的程序员，因为你只需要在日常工作或者面试中复习一下，而我完全是从头学起。不过，幸运的是，还不算太晚。在这里，我们就以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)从上面的代码可以看出，loopembedding集合的数量与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)级别。当然有些算法会占用非常大的空间复杂度，让你的内存分分钟炸飞。遇到这类算法，我们会单独说明空间复杂度。总结第一篇文章是基于理论方面的，也是学习数据结构和算法的实际情况，一定要理论结合实践。让我们从现在开始，向着这个无底洞的超级大坑进发吧！！参考资料：《数据结构》第2版，闫伟民《数据结构》第2版，陈越《数据结构高分笔记》2020年版，天琴考研============各媒体平台均可搜索【硬核项目经理】】
