数据结构和算法：简介

2025-06-07

数据结构和算法：简介

我知道你很努力。

你有 100 个不同的副项目。

由于这些提交，您的 GitHub 全部为绿色。

然后，你的日子终于到来了，你终于得到了面试机会。

您观看了一些有关技术面试的视频。

现实打击...

你对数据结构和算法一无所知。

别担心，几天前我也和你一样，但我失败了……

但我不希望你失败。

因此在这个新系列中，我将成为你们的新数据结构和算法老师。

附言：不幸的是，我还没有在谷歌工作，但我对这个主题还是略知一二的。

目录

为什么要学习数据结构？

这个问题问得非常有道理，因为我们生活在一个90%代码都会用到库函数的时代。主要有以下四个原因：

  1. 理解这些抽象行为背后的逻辑。如果不理解，你最终会以一种伤害自身的方式应用它们。
  2. 理解算法能帮助你理解这些算法旨在解决哪些问题。这种理解将极大地帮助你的日常工作，因为这些问题是基本的逻辑和计算机科学问题，无论你开发的是商业软件、硬件驱动程序、游戏还是移动应用，它们都随处可见。
  3. 您需要了解算法和数据结构，因为我见过不了解这些的人编写的代码；相信我，您不会想成为这样的人。
  4. 大多数顶级产品公司都会问与算法和数据结构相关的问题。你可能会想，为什么面试官会如此关注数据结构分析（DSA），而不是语言/框架/工具？因为这些公司面临的问题与你通常遇到的不一样，他们要处理的问题更复杂，规模也更大。所以，重要的不是解决问题本身，而是正确地解决问题。

什么是数据结构？

还记得小时候，因为在凌乱的房间里找不到衣服，父母会责骂你吗？事实证明，父母说的没错，保持房间整洁，这样下次找东西的时候就会容易得多。作为人类，我们早已明白在现实生活中整理（结构化）物品（数据）的重要性。

另一个很好的例子是图书馆。想象一下，你需要找一本关于俄罗斯历史的书，你会先去历史区，然后再去俄语区。如果这些书没有整理好，你就很难找到你想要的书，这会是一个非常令人沮丧的过程。

简而言之，数据结构是指我们组织数据的方式。

让我们考虑一些例子：

  • Facebook（你最喜欢的应用）。你所有的朋友、家人、共同的朋友以及朋友的朋友都可以用一张图来表示。想一想，用这种方式来表示 Facebook 上的好友完全合理。
  • 假设你有一副牌，你需要把它摆放整齐。你可以随机扔牌，也可以把牌一张叠一张地摆放，组成一副合适的牌。这时，你可以用一叠牌来把牌摆放整齐。
  • 如果你想在字典里找一个单词，你会怎么做？是一页一页地翻，还是翻到中间，如果找不到，再翻到上一页/后一页。我们这里使用二分查找法来高效地找到单词。

在前两个例子中，我们选择了正确的数据结构来表示现实世界的数据，而第三个例子选择了正确的算法来节省我们的时间和空间。

抽象数据类型与数据结构

抽象数据类型是数据结构的抽象，它仅提供数据结构必须遵守的接口。

该接口没有提供关于如何实现某些东西或使用什么编程语言的具体细节。

简而言之，ADT（抽象数据类型）更具逻辑描述，而数据结构则具体。

将 ADT 视为数据以及操纵和改变数据的操作的图像。

数据结构是真实存在的、具体的事物。它可以在算法中实现和使用。

替代文本

计算复杂性分析

作为程序员，我们不断问这两个问题：

  1. 这个算法需要多少时间才能完成？
  2. 该算法的计算需要多少空间？

基本上，如果出现以下情况，那就糟糕了：

  1. 如果你的算法很小，但需要花费宇宙的时间来计算。
  2. 您的算法速度很快，但需要地球上所有机器的计算能力。

大O符号

Big-O 符号给出了最坏情况下复杂度的上限，有助于量化输入大小任意增大时的性能。

基本上，它展示了算法的最坏情况。例如，你可能有一个排序算法。然后，大 O 符号将基于一个庞大的列表计算复杂度。

另一个例子可能是，你有一个算法来寻找数字 7。Big-O 将进行计算，但它会假定数字 7 位于列表的末尾。

Big-O 不关心小输入，它只关心大输入。

替代文本

Big-O 符号表（从最好到最差）（n = 输入大小）

Big-O 符号属性

替代文本

前两个性质解释了为什么我们可以简单地移除常数值 (c)，因为如果将一个常数加到无穷大上，结果就等于无穷大。乘法也一样。

但这只是理论上的，在现实世界中，如果常数是 20 亿，你就不能忽略它。

后半部分主要介绍了一个数学函数，并展示了如何得到大 O 符号。基本前提是取最大的 n，在我们的例子中是 n^3。

时间复杂度

现在我们将分解时间复杂度的基础知识（常数、线性、二次、指数和对数）。当然还有其他一些复杂度，但一旦你掌握了主要的几个，其他的就很容易理解了。

O(1) — 常数

恒定时间复杂度描述的是一种无论输入大小如何，总是花费相同时间（或空间）的算法。例如，在 JavaScript 中，这可以像访问数组中的特定索引一样简单：

var array = [1, 2, 3, 4, 5];
array[0] // This is a constant time look-up

var numberOfElementsToRemove = 2;while (numberOfElementsToRemove > 0) {
    array.pop();
   //This will also have a constant time look-up since the function 
   //is only looking at a specific reference point within the array.
  }
};
Enter fullscreen mode Exit fullscreen mode

无论输入是 5 还是 500 万，计算所需的时间都是一样的。

O（n）——线性时间

线性时间描述的是一种算法，其计算能力与输入大小成正比。例如，如果你想打印出一个数组中的所有元素，从逻辑上讲，数组越大，计算所需的时间就越长。

var numberRange = function(array) {
  for (var i = 1; i < array.length; i++) {
    console.log(array[i]);
  }
};
Enter fullscreen mode Exit fullscreen mode

O（log n）——对数时间

对数时间描述的是一种算法，其运行速度与输入的对数成正比。我知道一开始可能有点令人困惑，但让我给你举个例子。你想在电话簿里查找某个名字，显然不需要逐个检查所有名字。你只需根据名字的字母顺序进行分治即可。（这是一个二分查找，所以它的时间复杂度是 O(log n)）

这个时间复杂度有两个属性：

  1. 选择下一个要执行某些操作的元素是几种可能性之一。
  2. 只需选择一个。
for (var i = 1; i < n; i = i * 2){
    console.log("Hey - I'm busy looking at: " + i);
}
Enter fullscreen mode Exit fullscreen mode

如果n为 8，则输出如下：

Hey - I'm busy looking at: 1
Hey - I'm busy looking at: 2
Hey - I'm busy looking at: 4
Enter fullscreen mode Exit fullscreen mode

我们的简单算法运行了 log(8) = 3 次。

要找到更多示例，只需查看使用分治法的算法，如二分搜索、合并排序、快速排序等......

一般来说，该算法比 O(n) 更好，这是有道理的，因为 log(n) 总是比 n 小，小得多。

O(n^2) — 二次时间

二次时间描述的是一种算法，其运行时间与输入大小的平方成正比。通常情况下，这非常糟糕，但说实话，如果你的输入量不是很大，那也无所谓。

function quadraticSum(num){
    for (i = 0; i <= num; i++){
               for (j = 0; j < num; j++){
                   sum += j;
               }
           }
}
Enter fullscreen mode Exit fullscreen mode

在这个例子中，我们每 n 个元素查找两次数组，基本上就是 n^2。我认为在需要查找两次的算法中可以找到类似的例子，比如冒泡排序。

O(2^n) — 指数时间

指数时间复杂度指的是一种算法，其每次增加输入数据集时，其增长速度都会翻倍。如果你了解其他指数增长模式，其原理大致相同。时间复杂度一开始非常浅，然后以不断增加的速度上升，直到最终结束。指数时间算法通常是递归算法，通过递归求解规模为 n-1 的子问题来解决规模为n的问题。

var fibonacci = function(number) {
  if (number <= 1) return number;
  return Fibonacci(number - 2) + Fibonacci(number - 1);
}; //This will have an exponential time look-up since the function 
   //is looking at a every index an exponential number of times.
Enter fullscreen mode Exit fullscreen mode

斐波那契数列是练习递归理解的好方法。虽然有办法降低斐波那契函数的时间复杂度，但在本例中，我们将使用双重递归方法来展示它如何具有指数时间复杂度。在这里，我们通过递归调用大小分别为n-1和n-2的相同函数来解决大小为 n 的主要问题。

结论

我知道我们还没有讨论任何具体的数据结构或算法，但我认为有必要先讨论一下基础知识。总之，我希望你今天学到了一些东西，不久的将来，我们会在各自的文章中详细分析具体的数据结构。

PS：有任何疑问欢迎在下方留言，我很乐意解答😃

其他参考

文章来源：https://dev.to/tamerlan_dev/data-structs-and-algorithms-introduction-9mo
Devto 翻译
PREV
Scrapebase + Permit.io：授权网页抓取
NEXT
别再用 if-else 语句了！策略模式和工厂模式结合使用