网站建设的词58同城赶集网
第一章:算法与数据结构要点速学
1.时间复杂度 (大 O)
首先，我们来谈谈常用操作的时间复杂度，按数据结构/算法划分。然后，我们将讨论给定输入大小的合理复杂性。
数组（动态数组/列表）
规定 n = arr.length,
注意: 𝑂(1)O(1) 操作相对于
n是常数.实际上，哈希算法可能代价很高。例如，如果你的键是字符串，那么它将花费 𝑂(𝑚)O(m)，其中 𝑚m 是字符串的长度。 这些操作只需要相对于哈希映射大小的常数时间。
上面的说明也适用于这里。
-
在结尾添加或删除元素: 𝑂(1)O(1) 相关讨论
-
从任意索引中添加或删除元素: 𝑂(𝑛)O(n)
-
访问或修改任意索引处的元素: 𝑂(1)O(1)
-
检查元素是否存在: 𝑂(𝑛)O(n)
-
双指针: 𝑂(𝑛⋅𝑘)O(n⋅k), 𝑘k 是每次迭代所做的工作，包括滑动窗口
-
构建前缀和: 𝑂(𝑛)O(n)
-
求给定前缀和的子数组的和：𝑂(1)O(1)
字符串 (不可变)
规定
n = s.length, - 添加或删除字符: 𝑂(𝑛)O(n)
- 任意索引处的访问元素: 𝑂(1)O(1)
- 两个字符串之间的连接: 𝑂(𝑛+𝑚)O(n+m), 𝑚m 是另一个字符串的长度
- 创建子字符串: 𝑂(𝑚)O(m), 𝑚m 是子字符串的长度
- 双指针: 𝑂(𝑛⋅𝑘)O(n⋅k), 𝑘k 是每次迭代所做的工作，包括滑动窗口
- 通过连接数组、stringbuilder 等构建字符串：𝑂(𝑛)O(n)
链表
给定 𝑛n 作为链表中的节点数，
- 给定指针位置的后面添加或删除元素: 𝑂(1)O(1)
- 如果是双向链表，给定指针位置添加或删除元素: 𝑂(1)O(1)
- 在没有指针的任意位置添加或删除元素: 𝑂(𝑛)O(n)
- 无指针任意位置的访问元素: 𝑂(𝑛)O(n)
- 检查元素是否存在: 𝑂(𝑛)O(n)
- 在位置
i和j之间反转: 𝑂(𝑗−𝑖)O(j−i) - 使用快慢指针或哈希映射完成一次遍历: 𝑂(𝑛)O(n)
哈希表/字典
给定
n = dic.length, - 添加或删除键值对: 𝑂(1)O(1)
- 检查 key 是否存在: 𝑂(1)O(1)
- 检查值是否存在: 𝑂(𝑛)O(n)
- 访问或修改与 key 相关的值: 𝑂(1)O(1)
- 遍历所有键值: 𝑂(𝑛)O(n)
集合
给定
n = set.length, - 添加或删除元素: 𝑂(1)O(1)
- 检测元素是否存在: 𝑂(1)O(1)
栈
栈操作依赖于它们的实现。栈只需要支持弹出和推入。如果使用动态数组实现:
给定 n = stack.length,
注意:大多数编程语言实现队列的方式比简单的双链表更复杂。根据实现的不同，通过索引访问元素可能比 𝑂(𝑛)O(n) 快，但有一个重要的常量除数。
- 推入元素: 𝑂(1)O(1)
- 弹出元素: 𝑂(1)O(1)
- 查看 (查看栈顶元素): 𝑂(1)O(1)
- 访问或修改任意索引处的元素: 𝑂(1)O(1)
- 检测元素是否存在: 𝑂(𝑛)O(n)
队列
队列操作依赖于它们的实现。队列只需要支持出队列和入队列。如果使用双链表实现:
给定
n = queue.length, - 入队的元素: 𝑂(1)O(1)
- 出队的元素: 𝑂(1)O(1)
- 查看 (查看队列前面的元素): 𝑂(1)O(1)
- 访问或修改任意索引处的元素: 𝑂(𝑛)O(n)
- 检查元素是否存在: 𝑂(𝑛)O(n)
二叉树问题 (DFS/BFS)
给定 𝑛n 作为树的节点数，
大多数算法的时间复杂度为 𝑂(𝑛⋅𝑘)O(n⋅k),𝑘k 是在每个节点上做的操作数, 通常是 𝑂(1)O(1)。这只是一个普遍规律，并非总是如此。我们在这里假设 BFS 是用高效队列实现的。
二叉搜索树
给定 𝑛n 作为树中的节点数，
- 添加或删除元素：最坏的情况下 𝑂(𝑛)O(n),平均情况 𝑂(log𝑛)O(logn)
- 检查元素是否存在：最坏的情况下 𝑂(𝑛)O(n),平均情况 𝑂(log𝑛)O(logn)
平均情况是当树很平衡时 —— 每个深度都接近满。最坏的情况是树只是一条直线。
堆/优先队列
给定 n = heap.length 并讨论最小堆,
- 添加一个元素: 𝑂(log𝑛)O(logn)
- 删除最小的元素: 𝑂(log𝑛)O(logn)
- 找到最小的元素: 𝑂(1)O(1)
- 查看元素是否存在: 𝑂(𝑛)O(n)
二分查找
在最坏的情况下，二分查找的时间复杂度为 𝑂(log𝑛)O(logn)，其中 𝑛n 是初始搜索空间的大小。
其他
- 排序: 𝑂(𝑛⋅log𝑛)O(n⋅logn), 其中 𝑛n 是要排序的数据的大小
- 图上的 DFS 和 BFS：𝑂(𝑛⋅𝑘+𝑒)O(n⋅k+e)，其中 𝑛n 是节点数，𝑒e 是边数，前提是每个节点处理花费都是 𝑂(1)O(1)，不需要重复遍历。
- DFS 和 BFS 空间复杂度：通常为 𝑂(𝑛)O(n)，但如果它在图形中，则可能为 𝑂(𝑛+𝑒)O(n+e) 来存储图形
- 动态规划时间复杂度：𝑂(𝑛⋅𝑘)O(n⋅k)，其中 𝑛n 是状态数，𝑘k 是每个状态所需要的操作数
- 动态规划空间复杂度：𝑂(𝑛)O(n)，其中𝑛n是状态数
2.输入大小与时间复杂度
3.排序算法
4. 通用 DS/A 流程图
