数据结构操作——时间复杂度

Created: March 19, 2024 12:34 PM

下面是一些C++中常见的数据结构或容器及其对于访问（Access）、插入（Insertion）、删除（Deletion）等操作的时间复杂度概览。请注意，这些时间复杂度是大致的，并且可能基于最坏情况（Worst case）或平均情况（Amortized/Expected）来表示。

动态数组（std::vector）

• 访问（通过索引）：O(1)
• 插入（末尾）：O(1) 平均；O(n) 最坏情况（需要重新分配时）
• 删除（末尾）：O(1)
• 插入/删除（任意位置）：O(n)（需要移动元素）

双端队列（std::deque）

• 访问（通过索引）：O(1)
• 插入/删除（头部或尾部）：O(1)
• 插入/删除（任意位置）：O(n)（需要移动元素）

列表（std::list）

• 访问（通过索引）：O(n)
• 插入/删除（任意位置）：O(1)（已有迭代器到目标位置）

前向列表（std::forward_list）（C++11）

• 访问（通过索引）：不支持直接索引访问
• 插入/删除（任意位置）：O(1)（已有迭代器到目标位置）

栈（std::stack）

• 访问（顶部元素）：O(1)
• 插入/删除（顶部元素）：O(1)

队列（std::queue）

• 访问（队首元素）：O(1)
• 插入（尾部）/删除（头部）：O(1)

优先队列（std::priority_queue）

• 访问（最大元素）：O(1)
• 插入：O(log n)
• 删除（最大元素）：O(log n)

关联容器（std::set, std::map）

• 访问/插入/删除：O(log n)

无序关联容器（std::unordered_set, std::unordered_map）（C++11）

• 访问/插入/删除：O(1) 平均；O(n) 最坏情况（哈希冲突）

这些时间复杂度提供了在选择特定数据结构或容器时考虑其性能特征的基础。不同的数据结构为不同的应用场景提供了优化，选择正确的结构对于实现高效的算法和程序至关重要。