2022PHP程序员修炼秘笈：计算机基础到操作系统

计算机基础

数据结构

是相互之间具有一种或多种特定关系的数据元素的集合❀上面的解释是学术晦涩的很难理解。首先，为什么我们需要创建这么多数据结构？核心原因是“需求”。不同的要求需要不同的要点。这里强调时间和空间的优化，不同的数据结构实际上权衡了时间和空间的分配。举个例子

以顺序表（数组）和单链表

首先，顺序表，顾名思义，就是顺序存储，所以顺序存储的优点是。由于其存储是连续的，访问速度很快。我们只需要把当前地址加1就可以访问下一个数组元素。但由于它的地址是连续的，所以我们删除该数组。并且增加，麻烦就更大。当我们要删除或添加一个数组元素时，我们需要将删除或添加位置之后的所有元素都移动，以保证它们的存储是连续的。

那么我们可以认为数组等数据结构适合要求查询速度快、占用空间小，但更新速度稍慢的需求。

相反，单链表

的每个节点都由内容和指向下一个节点（下一个）的地址指针组成。每个 next 都指向其下一个节点的地址。此时，相比于数组，由于每个内容需要两个地址块来存储，而相比于数组存储相同数量的单链表，它所占用的空间是数组的两倍。我们继续看单链表的更新和删除。 ，因为单向链表的每个元素都是由 next 维护的，所以我们只需要将待插入节点的 next 指针指向待插入节点的后一个节点的地址，然后设置该节点的 next 指针即可node previous node , to be insert 指向要插入节点的地址，完成更新操作。

那么我们可以认为单链表等数据结构适合需要快速查询和更新速率的应用，但可以接受牺牲一些存储的需要。

回到实际需求，数组和单链表的属性映射了现实生活中的很多需求点，比如

• 需要较快的查询速度，奖励规则的计算可能更新速度较慢
• 需要更新速度 用户支付结果实时快速更新，会占用较多空间 算法

  

  好的算法 与数据结构密切相关

  为什么算法与数据结构相关？首先，您需要了解为什么需要算法。那么什么是算法呢？

  算法需要更好地解决问题，那么它解决什么问题呢？和数据结构一样，平衡时间和空间的问题

  一个小学数学问题的例子

  (15 + 4) * 3 = ?

  你的数学老师一定教过你这个

  (15 * 3) + (4 * 3) = 57

  那你为什么要这么做呢？我们也可以制作原来的公式，因为第二种方法可以计算得更快。这就是我们上面说的解决时间问题

  举个简单的例子，分而治之是算法中常用的方法，就像减半一样。为了进行搜索，我们将矩阵分成两部分并同时检索要搜索的数据。那么它的速度是从头开始逐个搜索的两倍（忽略极端情况，命中第一个或最后一个）。相比二分查找和简单检索，二分查找提高了效率（即缩短了检索时间）

  当然，有一些算法是在特定的数据结构中必须使用的，比如大家熟知的二叉树。树搜索是经典的分而治之，在有序树的情况下，它的搜索时间复杂度是O(Log2n)，这意味着我们的平均搜索时间将是普通顺序检索的1倍甚至更高（忽略极端情况），但是二叉树的构造是由链表组成的。树中的左子节点标记和右子节点标记分别占用空间。这意味着一个树节点至少占用三个槽，而保持树处于有序状态需要牺牲更新。成本，那么我们可以认为树搜索的主要目的是提高查询速度，并且对更新和空间占用有一定的容忍度。

  推荐入门书籍《趣学算法》人民邮电出版社
  推荐在线课程王峥老师的