数据结构与算法

数据结构研究数据的表示、类型及相互关系，决定数据如何存储、访问和修改；算法是解决问题的一系列步骤。实际解题中需要先按问题特点组织数据，再选择能在约束内完成处理的算法。

1. 常见数据结构

结构	主要特点	典型场景
数组	按下标连续访问	顺序存储、前缀和、动态规划。
链表	节点通过链接组织	需要频繁调整连接关系的序列。
栈	后进先出	括号匹配、表达式处理、递归模拟。
队列	先进先出	广度优先搜索、按顺序处理任务。
树、图	表达层次或任意关系	层级结构、路径与连通性问题。

同一种问题可有不同实现，但数据组织方式会直接影响后续操作的成本。因此不能只看功能是否实现，也要比较查找、修改、遍历所需的时间和额外内存。

2. 时间复杂度与空间复杂度

时间复杂度描述输入规模 n 增大时运行时间的增长趋势；空间复杂度描述算法额外占用的内存。大 O 记号忽略常数系数和低阶项，重点比较增长阶。

复杂度	常见形式	规模增大时的特点
`O(1)`	固定次数操作	与 n 无关。
`O(log n)`	每次折半	增长很慢。
`O(n)`	一次完整遍历	通常适合大规模数据。
`O(n log n)`	高效排序	常见且通常可接受。
`O(n²)`、`O(n³)`	多层完整嵌套	需要严格控制 n。
`O(2ⁿ)`、`O(n!)`	枚举所有选择或排列	仅适合很小的 n。

复杂度分析要先确定基本操作的执行次数，并结合输入范围判断是否可行。除时间外，也应注意递归深度、辅助数组和容器带来的空间开销。

3. 多项式求值：从模拟到优化

设多项式为 a[0] + a[1]x + a[2]x² + ... + a[n]xⁿ。它展示了算法优化的核心：发现并复用中间结果，避免重复计算。

模拟法：对每一项单独计算 xⁱ。第 i 项要做 i 次乘法，总操作量约为 O(n²)。
递推法：利用 xⁱ = x · x^i-1，保存上一次的幂，每轮只乘一次，时间降为 O(n)，额外空间为 O(1)。
秦九韶（霍纳）法：将式子改写为 (...(a[n]x + a[n-1])x + ...)x + a[0]，从最高次系数开始反复“乘 x 再加系数”。

long long horner(const vector<long long>& a, long long x) {
    long long y = a.back();
    for (int i = static_cast<int>(a.size()) - 2; i >= 0; --i) {
        y = y * x + a[i];
    }
    return y;
}

def horner(a, x):
    y = a[-1]
    for coefficient in reversed(a[:-1]):
        y = y * x + coefficient
    return y

两段霍纳法代码都只扫描一次系数，因此时间为 O(n)，除输入系数外仅使用常数个变量，即额外空间为 O(1)。这种从直接模拟、保存状态到代数重写的过程，是分析和优化算法的重要方法。

4. 选择算法的检查清单

明确输入规模、数据范围和需要完成的操作。
估算时间复杂度，避免在大规模数据上使用指数或高次多项式算法。
检查额外空间是否能容纳数组、状态或递归调用。
处理边界：空数据、单个元素、下标范围、整数溢出和重复值。