第一章：算法与数据结构要点速学-灵析社区

1. 时间复杂度 (大 O)

首先，我们来谈谈常用操作的时间复杂度，按数据结构/算法划分。然后，我们将讨论给定输入大小的合理复杂性。

数组（动态数组/列表）

规定 n = arr.length,

在结尾添加或删除元素: O(1) 相关讨论
从任意索引中添加或删除元素: O(n)
访问或修改任意索引处的元素: O(1)
检查元素是否存在: O(n)
双指针: O(n⋅k), k 是每次迭代所做的工作，包括滑动窗口
构建前缀和: O(n)
求给定前缀和的子数组的和：O(1)

字符串 (不可变)

规定 n = s.length,

添加或删除字符: O(n)
任意索引处的访问元素: O(1)
两个字符串之间的连接: O(n+m), m 是另一个字符串的长度
创建子字符串: O(m), m 是子字符串的长度
双指针: O(n⋅k), k 是每次迭代所做的工作，包括滑动窗口
通过连接数组、stringbuilder 等构建字符串：O(n)

链表

给定n作为链表中的节点数，

给定指针位置的后面添加或删除元素: O(1)

如果是双向链表，给定指针位置添加或删除元素: O(1)

在没有指针的任意位置添加或删除元素: O(n)

无指针任意位置的访问元素: O(n)

检查元素是否存在: O(n)

在位置 i 和j 之间反转: O(j−i)

使用快慢指针或哈希映射完成一次遍历: O(n)

哈希表/字典

给定 n = dic.length,

添加或删除键值对: O(1)
检查 key 是否存在: O(1)
检查值是否存在: O(n)
访问或修改与 key 相关的值: O(1)
遍历所有键值: O(n)

注意: O(1) 操作相对于 n 是常数.实际上，哈希算法可能代价很高。例如，如果你的键是字符串，那么它将花费 O(m)，其中 m 是字符串的长度。这些操作只需要相对于哈希映射大小的常数时间。

集合

给定 n = set.length,

添加或删除元素: O(1)

检测元素是否存在: O(1)

上面的说明也适用于这里。

栈

栈操作依赖于它们的实现。栈只需要支持弹出和推入。如果使用动态数组实现:

给定 n = stack.length,

推入元素: O(1)
弹出元素: O(1)
查看 (查看栈顶元素): O(1)
访问或修改任意索引处的元素: O(1)
检测元素是否存在: O(n)

队列

队列操作依赖于它们的实现。队列只需要支持出队列和入队列。如果使用双链表实现:

给定 n = queue.length,

入队的元素: O(1)
出队的元素: O(1)
查看 (查看队列前面的元素): O(1)
访问或修改任意索引处的元素: O(n)
检查元素是否存在: O(n)

注意:大多数编程语言实现队列的方式比简单的双链表更复杂。根据实现的不同，通过索引访问元素可能比 O(n) 快，但有一个重要的常量除数。

二叉树问题 (DFS/BFS)

给定 n 作为树的节点数，

大多数算法的时间复杂度为 O(n⋅k),k 是在每个节点上做的操作数, 通常是 O(1)。这只是一个普遍规律，并非总是如此。我们在这里假设 BFS 是用高效队列实现的。

二叉搜索树

给定 n 作为树中的节点数，

添加或删除元素：最坏的情况下 O(n),平均情况 O(log n)
检查元素是否存在：最坏的情况下 O(n),平均情况 O(logn)

平均情况是当树很平衡时 —— 每个深度都接近满。最坏的情况是树只是一条直线。

堆/优先队列

给定 n = heap.length 并讨论最小堆,

添加一个元素: O(logn)
删除最小的元素: O(logn)
找到最小的元素: O(1)
查看元素是否存在: O(n)

二分查找

在最坏的情况下，二分查找的时间复杂度为 O(logn)，其中 n 是初始搜索空间的大小。

其他

排序: O(n⋅logn), 其中 n 是要排序的数据的大小

图上的 DFS 和 BFS：O(n⋅k+e)，其中 n 是节点数，e 是边数，前提是每个节点处理花费都是 O(1)，不需要重复遍历。

DFS 和 BFS 空间复杂度：通常为 O(n)，但如果它在图形中，则可能为 O(n+e) 来存储图形

动态规划时间复杂度：O(n⋅k)，其中 n 是状态数，k 是每个状态所需要的操作数

动态规划空间复杂度：O(n)，其中n是状态数

2. 输入大小与时间复杂度

问题的约束可以被视为提示，因为它们指示解决方案时间复杂度的上限。能够在给定输入大小的情况下计算出解决方案的预期时间复杂度是一项宝贵的技能。在所有 LeetCode 问题和大多数在线评估 (OA) 中，你都会得到问题的约束条件。不幸的是，你通常不会在面试中被明确告知问题的限制条件，但这对于在 LeetCode 上练习和完成 OAs 仍然有好处。尽管如此，在面试中，询问预期的输入大小通常也没什么坏处。

n <= 10

预期的时间复杂度可能具有基数大于“2”的阶乘或指数 - 例如 O(n² ⋅n!) 或 O(4 ⁿ)。

您应该考虑回溯或任何蛮力式递归算法。 n <= 10 非常小，通常任何正确找到答案的算法都足够快。

10 < n <= 20

预期的时间复杂度可能涉及 O(2 ⁿ )。任何更高的基数或阶乘都会太慢（3²⁰= ~35 亿，20! 更大）。 2 ⁿ通常意味着给定一个元素集合，您正在考虑所有子集/子序列 - 对于每个元素，有两种选择：接受或不接受。

同样，这个界限非常小，所以大多数正确的算法可能足够快。考虑回溯和递归。

20 < n <= 100

在这一点上，指数将太慢。上限可能是 O(n³)。

LeetCode 上标记为「简单」的问题通常有这个界限，这可能是骗人的。可能存在以 O(n) 运行的解决方案，但小边界允许蛮力解决方案通过（找到线性时间解决方案可能不被视为「容易」）。

考虑涉及嵌套循环的强力解决方案。如果你想出了一个蛮力解决方案，请尝试分析算法以找出哪些步骤“慢”，并尝试使用哈希映射或堆等工具改进这些步骤。

100 < n <= 1,000

在此范围内，只要常数因子不太大，时间复杂度 O(n ² ) 就足够了。与前面的范围类似，你应该考虑嵌套循环。这个范围和前一个的区别在于，O(n ²) 通常是这个范围内的预期/最优时间复杂度，可能无法提高。

1,000 < n < 100,000

n<=10 ⁵是你在 LeetCode 上看到的最常见的约束。在此范围内，可接受最慢的通常时间复杂度为 O(n⋅logn)，尽管线性时间方法 O(n) 更为常见。

在此范围内，问问自己对输入进行排序或使用堆是否有帮助。如果不是，则瞄准 O(n) 算法。在 O(n² ) 中运行的嵌套循环是不可接受的 - 你可能需要使用在本课程中学到的技术来实现 O(1) 或 O(logn):

哈希映射
类似于滑动窗口的两指针实现
单调堆栈
二分搜索
堆
以上任何一项的组合

如果你有一个 O(n) 算法，常数因子可以相当大（大约 40）。字符串问题的一个常见主题涉及在每次迭代时遍历字母表中的字符，导致时间复杂度为 O(26n)。

100,000 < n < 1,000,000

n<=10 ⁶ 是一个罕见的约束，可能需要 O(n) 的时间复杂度。在这个范围内，O(n⋅logn) 通常是安全的，只要它有一个小的常数因子。你很可能需要以某种方式合并哈希映射。

1,000,000 < n

对于巨大的输入，通常在 10 ⁹或更多的范围内，最常见的可接受时间复杂度将是对数 O(logn) 或常量 O(1)。在这些问题中，您必须要么在每次迭代时显着减少搜索空间（通常是二分搜索），要么使用巧妙的技巧在恒定时间内查找信息（例如使用数学或巧妙地使用哈希映射）。

其他时间复杂度也是可能的，例如 O( n )，但这种情况非常罕见，通常只会出现在非常高级的问题中。

3. 排序算法

所有主要的编程语言都有一个内置的排序方法。假设并说排序成本为 O(n⋅logn)。通常是正确的，其中 n 是要排序的元素数。为了完整起见，这里有一个图表，列出了许多常见的排序算法及其完整性。编程语言实现的算法各不相同；例如，Python 使用 Timsort，但在 C++ 中，特定算法不是强制性的并且会有所不同。

来自 Wikipedia

的稳定排序的定义："Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list."

4.通用 DS/A 流程图

这是一个流程图，可以帮助您确定应该使用哪种数据结构或算法。请注意，此流程图非常笼统，因为不可能涵盖每个场景。

请注意，此流程图仅涵盖 LICC 中教授的方法，因此排除了像 Dijkstra 等更高级的算法。