时间复杂度 (大 O)

![[Pasted image 20240429194251.png]]

![[Pasted image 20240429194302.png]]

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

数组(动态数组/列表)

规定 n = arr.length,

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

字符串 (不可变)

规定 n = s.length,

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

链表

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

  • 给定指针位置的后面添加或删除元素: 𝑂(1)
  • 如果是双向链表,给定指针位置添加或删除元素: 𝑂(1)
  • 在没有指针的任意位置添加或删除元素: 𝑂(𝑛)
  • 无指针任意位置的访问元素: 𝑂(𝑛)
  • 检查元素是否存在: 𝑂(𝑛)
  • 在位置 i 和 j 之间反转: 𝑂(𝑗−𝑖)
  • 使用快慢指针或哈希映射完成一次遍历: 𝑂(𝑛)

哈希表/字典

给定 n = dic.length,

  • 添加或删除键值对: 𝑂(1)
  • 检查 key 是否存在: 𝑂(1)
  • 检查值是否存在: 𝑂(𝑛)
  • 访问或修改与 key 相关的值: 𝑂(1)
  • 遍历所有键值: 𝑂(𝑛)
    1
    注意: 𝑂(1)O(1) 操作相对于 n 是常数.实际上,哈希算法可能代价很高。例如,如果你的键是字符串,那么它将花费 𝑂(𝑚)O(m),其中 𝑚m 是字符串的长度。 这些操作只需要相对于哈希映射大小的常数时间。

集合

给定 n = set.length,

  • 添加或删除元素: 𝑂(1)
  • 检测元素是否存在: 𝑂(1)
    1
    上面的说明也适用于这里。

栈操作依赖于它们的实现。栈只需要支持弹出和推入。如果使用动态数组实现:给定 n = stack.length,

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

队列

队列操作依赖于它们的实现。队列只需要支持出队列和入队列。如果使用双链表实现:给定 n = queue.length,

  • 入队的元素: 𝑂(1)
  • 出队的元素: 𝑂(1)
  • 查看 (查看队列前面的元素): 𝑂(1)
  • 访问或修改任意索引处的元素: 𝑂(𝑛)
  • 检查元素是否存在: 𝑂(𝑛)
    1
    注意:大多数编程语言实现队列的方式比简单的双链表更复杂。根据实现的不同,通过索引访问元素可能比 𝑂(𝑛)O(n) 快,但有一个重要的常量除数。

二叉树问题 (DFS/BFS)

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

二叉搜索树

给定 𝑛 作为树中的节点数,

  • 添加或删除元素:最坏的情况下 𝑂(𝑛),平均情况 𝑂(log⁡𝑛)
  • 检查元素是否存在:最坏的情况下 𝑂(𝑛), 平均情况 𝑂(log⁡𝑛)
    平均情况是当树很平衡时 —— 每个深度都接近满。最坏的情况是树只是一条直线。

堆/优先队列

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

  • 添加一个元素: 𝑂(log⁡𝑛)
  • 删除最小的元素: 𝑂(log⁡𝑛)
  • 找到最小的元素: 𝑂(1)
  • 查看元素是否存在: 𝑂(𝑛)

二分查找

在最坏的情况下,二分查找的时间复杂度为 𝑂(log⁡𝑛),其中 𝑛 是初始搜索空间的大小。

其他

  • 排序: 𝑂(𝑛⋅log⁡𝑛), 其中 𝑛 是要排序的数据的大小
  • 图上的 DFS 和 BFS:𝑂(𝑛⋅𝑘+𝑒),其中 𝑛 是节点数,𝑒 是边数,前提是每个节点处理花费都是 𝑂(1),不需要重复遍历。
  • DFS 和 BFS 空间复杂度:通常为 𝑂(𝑛),但如果它在图形中,则可能为 𝑂(𝑛+𝑒) 来存储图形
  • 动态规划时间复杂度:𝑂(𝑛⋅𝑘),其中 𝑛 是状态数,𝑘 是每个状态所需要的操作数
  • 动态规划空间复杂度:𝑂(𝑛),其中 𝑛 是状态数