数据结构与算法

1.基础

1.1 存储结构

• 数组：
  • 数据连续存储
  • 支持随机访问，通过索引快速找到对应元素，时间复杂度 $O(1)$
  • 数组满时需要扩容，重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 $O(n)$
  • 在数组中间进行插入和删除时需要对后面的所有数据进行移位，平均时间复杂度 $O(n)$
• 链表：
  • 数据不连续存储，而是靠指针指向其他元素的位置
  • 不支持随机访问，平均时间复杂度 $O(n)$
  • 无需扩容
  • 插入和删除时无需移位，时间复杂度 $O(1)$（前驱结点已知），$O(n)$（前驱结点未知）
  • 指针域会占用储存空间，降低空间利用率

1.2 逻辑结构

• 栈（stack）：后进先出（LIFO）。
• 队列（queue）：先进先出（FIFO）。
• 树（tree）：子结点也是一棵树，子结点之间相互独立。
• 图（graph）：任意两个结点间可以连接。

每种逻辑结构均可使用不同存储结构实现，一般具体情况进行选择。

1.3 复杂度

• 常见时间复杂度：$O(1)$、$O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$、$O(n^3)$
• 常见空间复杂度：$O(1)$、$O(n)$、$O(n^2)$、$O(n^3)$

复杂度一般去掉常数项，并将系数置为1，$O$ 表示上界。

1.4 可视化

• 数据结构和算法动态可视化
• Data Structure Visualizations

排序

算法-排序