c++数据结构常见算法的复杂度

### C++ 中常见数据结构及其时间和空间复杂度

#### 数组 (Array)

数组是一种线性的数据结构，在内存中连续存储相同类型的元素。

- **访问时间复杂度**: O(1)，因为可以通过索引直接定位到任何位置的元素[^4]。
- **查找时间复杂度**: 如果不知道确切的位置，则最坏情况下需要遍历整个数组，即O(n)。
- **插入/删除时间复杂度**: 插入或移除首部或中间某个特定位置上的元素会涉及到后续所有元素向左或右移动一位的操作，平均情况下的时间复杂度为O(n)；但在尾端进行这些操作时可以达到O(1)。
- **空间复杂度**: 需要预先分配固定大小的空间给定长度的数组，因此其空间复杂度为O(n)。

int arr[5]; // 定义了一个含有五个整型变量的数组

#### 链表 (Linked List)

链表由一系列节点组成，每个节点包含两部分：一部分用于保存数据项，另一部分是指向下个结点地址链接指针。

- **访问时间复杂度**: 访问任意指定位置处的数据需从头开始逐一遍历直到目标位置，故而具有O(n)的时间开销。
- **查找时间复杂度**: 类似于访问操作，同样具备O(n)级别的效率。
- **插入/删除时间复杂度**: 对于已知位置而言，只需改变前后相邻两个节点间的连接关系即可完成相应动作，此过程仅消耗常量级时间成本O(1); 不过如果未知具体位置则仍需先经历一次完整的扫描流程以确定待处理对象的确切地点，整体来看依旧维持着O(n)的数量级性能表现。
- **空间复杂度**: 每增加一个新的节点就会额外占用一块新的存储单元，所以总体来说它的空间需求随着列表的增长呈线性增长趋势，记作O(n)。

struct Node {
    int data;
    struct Node* next;  
};
Node* head = NULL;  // 初始化为空链表

#### 栈 (Stack)

栈遵循后进先出原则(LIFO, Last In First Out), 只允许在一侧（顶部）执行压入(push) 和弹出(pop) 的操作。

- **推入(Push)/弹出(Pop)**: 这些都是针对堆顶元素来进行增删改查的动作，由于每次变动只涉及单个成员单位的变化而不牵扯到底层其它成分的影响范围之内，因而它们各自所需付出的工作量均为固定的数值——也就是常说的那个“恒定时间内搞定”的意思啦！简单来讲就是O(1)。
- **获取栈顶(Top)**: 同样道理，读取当前位于顶端那个家伙的信息也只要瞬间就能办妥哦～依旧是O(1)。
- **判断是否为空(IsEmpty)**: 判断条件非常直观明了，要么里面啥都没有嘛就返回true表示确实空无一物咯；反之只要有哪怕一点点东西存在那就得报false说明不是完全空白的状态呢。显然这样的逻辑判定也不过是一眨眼之间的事情而已，属于典型的O(1)级别运算速度范畴内。
- **空间复杂度**: 当然啦，每当我们往里边塞进去一件新玩意儿的时候总归是要占据一定物理空间滴，不过好在这个增量始终保持着稳定不变的比例关系，不会突然暴涨暴跌什么的，所以我们可以说栈这种东东的空间耗费也是按照输入规模n成正比变化着，即O(n)。

#include <stack>
std::stack<int> s; 
s.push(1);
if (!s.empty()) std::cout << "Top element is " << s.top() << '\n';
s.pop();

#### 队列 (Queue)

队列采用先进先出策略(FIFO, First In First Out)，意味着最早加入队伍的人最先被服务完毕离开现场。

- **入队(Enqueue)**: 将新来的客人安排到最后面排队等候入场许可的过程叫做入队，这项工作基本上可以在瞬息万变之中顺利完成，几乎不费吹灰之力便能达成目的，因此我们将其视为拥有O(1)这样令人羡慕不已的速度优势。
- **出队(Dequeue)**: 轮到了谁家孩子该上前一步接受考验并光荣退场之时，这一系列动作同样能够迅速高效地被执行下去直至结束为止，全程耗时不超乎寻常之外，依然保持在O(1)这样一个让人惊叹不已的高度之上。
- **查看队首(front)** / **查看队尾(rear)** : 查看即将轮到或是最后一名等待者的身份信息同样是轻而易举之事，无需过多周折便可知晓真相大白于天下，自然也就归属于那批享有O(1)特权待遇的小团体当中的一员了。
- **判空(isEmpty)**: 此外还有用来检测此时此刻究竟有没有人在排队的一项功能，它所依赖的基础原理十分朴素直白易于理解掌握，完全可以做到立竿见影般的效果呈现出来，毫无疑问这也是一项能够在极短周期内给出答案的任务之一，对应的时间复杂度当然还是那位熟悉的面孔——O(1)。
- **空间复杂度**: 然而对于那些不断涌入的新访客们来说，每一个个体都需要为自己争取到属于自己的一席之地才行啊，这样一来随着人数增多必然会引起对于场地面积的需求同步扩大开来，最终形成一种与参与人员总数相匹配的关系模式，换句话说就是说队列的整体空间占有状况大致呈现出O(n)的趋势特征。

#include <queue>
std::queue<int> q;
q.push(1);
while (!q.empty()) { std::cout << q.front(); q.pop();}

#### 树(Tree)

树形结构是由多个分支构成的一种层次化组织形式，其中根节点处于最高层级并向四周扩散生长子代节点。

- **搜索(Searching)**: 寻找某一特定值可能存在于哪一层哪个分枝下面往往取决于具体的实现方式以及平衡程度等因素影响较大，理想状态下二叉搜索树(BST)可在log₂n次比较之后锁定目标所在之处，然而当遇到极端不平衡的情况时可能会恶化至接近线性水平O(n)。
- **插入(Insertion)**: 新添叶子节点的行为类似于上述提到过的搜寻路径机制，正常情形下亦能达到对数阶别的效能指标O(log n)，但前提是没有发生严重的倾斜现象破坏原有秩序而导致效率下降严重的问题出现。
- **删除(Removal)**: 移走已经存在的记录条目除了要考虑如何重新调整内部关联以外还要兼顾外部形态美观与否等诸多方面的要求，所以在某些特殊条件下或许难以避免会出现较为复杂的局面从而使得实际运行过程中表现出更差一点的表现特性比如说是介于两者之间的状态或者是干脆变成了纯粹意义上的顺序排列那样糟糕的结果O(n)。
- **空间复杂度**: 构建一棵满二叉树的话理论上最多只需要大约等于2^(h+1)-1个节点数量(h代表高度)，考虑到实际情况并非总是如此完美无缺的缘故，一般认为树状体系内的空间利用效率大概率会在O(n)附近徘徊不定。

// 示例代码省略，因不同种类树木的具体编码差异很大