认识算法和数据结构

1、算法（Algorithm）

是什么

简单来说：通过一系列明确、有限且有序的步骤集合，解决特定问题并给出结果的过程。

算法（Algorithm）是一个明确的步骤或规则集，用于解决特定问题或执行任务，可以视为一系列的操作指导，按照一定的顺序和逻辑实现某个目标。

算法的关键特点

• 输入：算法开始时的初始数据。
• 输出：经过算法计算后的结果。
• 有限性：算法必须在有限的步骤内终止。
• 确定性：每一步都必须明确无歧义。
• 有效性：每步操作必须是可行的。

算法应用

例如 react 的 diff 算法、webpack 中利用 tree-shaking 优化、v8 中的调用栈、消息队列等

算法复杂度

2、数据结构

是什么

数据结构（Data Structure）是指在计算机中组织和存储数据的方式

不仅涉及数据的存储方式，还包括数据的操作方法。

数据结构决定了数据的组织形式、存储顺序以及如何高效地进行数据插入、删除、查找和更新等操作。

根据需求不同，选择不同的数据结构来解决问题，能够提高程序的效率和性能。

分类

根据其特点和用途，数据结构可以大致分为以下几类

✨线性数据结构

线性数据结构是指数据元素之间有顺序关系，每个数据元素只有一个前驱和一个后继

• 数组（Array）：
  • 数组是最基本的数据结构，用于存储固定大小的元素集合。它的特点是元素在内存中是连续存储的，可以通过索引直接访问任意位置的元素。
  • 优点：访问速度快，支持随机访问。
  • 缺点：大小固定，插入和删除操作效率较低（除非在数组末尾）。
• 链表（Linked List）：
  • 链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的元素不一定是连续存储的，而是通过指针连接起来的。
  • 优点：插入和删除操作比较高效，尤其是在已知位置时。
  • 缺点：访问特定元素时需要从头节点开始遍历，效率较低。
• 栈（Stack）：
  • 栈是一种后进先出（LIFO, Last In First Out）数据结构。栈的操作主要有两个：push（入栈）和 pop（出栈）。
  • 应用：例如，程序的递归调用、浏览器的历史记录、括号匹配等。
• 队列（Queue）：
  • 队列是一种先进先出（FIFO, First In First Out）数据结构。队列的操作有两个：enqueue（入队）和 dequeue（出队）。
  • 应用：任务调度、消息队列、宽度优先搜索等

✨非线性数据结构

非线性数据结构是指数据元素之间没有固定的顺序关系。常见的非线性数据结构包括：

• 树（Tree）：
  • 树是一种层次结构的数据结构，由一个根节点和多个子节点组成。每个节点可以有零个或多个子节点，且没有环路。
  • 应用：例如，文件系统、数据库索引、组织结构图等。
• 图（Graph）：
  • 图由节点和边组成，节点表示数据元素，边表示节点之间的关系。图可以是有向图（有方向的边）或无向图（没有方向的边）。
• 应用：如社交网络分析、网络路由、依赖关系图等。

✨哈希结构

• 哈希表（Hash Table）：
  • 哈希表是一种基于哈希函数的数据结构，利用哈希函数将数据映射到数组的索引位置。它具有非常高的查找效率，理想情况下是常数时间复杂度（O(1)）
  • 应用：例如，数据库的索引、缓存等。

常见数据结构

• 数组：存储学生的成绩单，快速查找某个成绩。
• 链表：实现浏览器的历史记录（后退和前进操作）。
• 栈：实现递归、表达式求值（如括号匹配）。
• 队列：任务调度系统、打印队列。
• 树：文件系统（目录结构）、数据库索引。
• 图：社交网络分析、交通路网、依赖关系管理。
• 哈希表：缓存系统、数据库索引。