跳转到内容
- 程序 = 数据结构 + 算法。
- 数据：外界信息进入计算机后的统称，分数值型（int, float）与非数值型（bool, char, string）；数据元素：数据处理的基本单位，通常作为整体处理的一个数据个体；不可再分的字段通常称为数据项。
- 数据结构：一组具有特定关系的同类数据元素的集合；研究内容 = 逻辑结构 + 存储结构 + 基本操作。
- 算法：解决一个具体问题的方法和步骤。
- 集合关系——同属一个集合、相互无其他关系、次序任意；线性关系——你先我后的一对一；树形关系——一对多；图关系——多对多。
- 前驱/后继：线性结构除队首均有唯一前驱、除队尾均有唯一后继；树中除根均有唯一前驱、可有多个后继；图中前驱与后继都可有多个。
- 创建、清除、插入（增）、删除（删）、更新（改）、查找（查）、遍历（每个元素仅被访问一次）。
- 内存中既存元素的值，也存元素间的关系；操作的设计取决于逻辑结构，操作的实现依赖存储结构；存储方式要有利于基本操作的实现。
- 顺序存储（数组）：连续空间，用地址有序性隐式表关系；元素地址 a+i·k（k 为单元素所占空间）。优：按序号直接访问；劣：需预先声明大小、需连续空间、插入删除效率低。
- 链式存储（链表）：空间不要求连续，关系经指针域显式存储，链尾指针为 NULL。优：长度可动态变化、插入删除高效、存储利用率高；劣：不能按序号访问需从头遍历、每个元素额外耗一个指针域。
- 随机查询极多、插入删除极少时选数组。
- 五特性：确定性（无二义）、有穷性（有限步内完成）、可行性（有限次基本操作可完成）、有输入（零或若干个）、有输出（通常一个或若干个可观察输出/效果）。
- 五要求：正确性、可读性、健壮性（注意边界条件与特殊值）、时间效率（TLE）、空间效率（MLE）。
- 影响运行时间的因素：问题规模、算法优劣（两项为重点）、编译器代码质量、计算机系统性能。
- 时间频度 T(n)：基本语句的实际执行次数（循环按实际运行次数计；分支按执行语句多的分支计）。例
s=0; for(i=0;i<n;i++) s=s+i; → T(n)=3n+3。
- 大 O 定义：存在常数 C 与 N0，当 N>N0 时 T(N)≤C⋅F(N)，则记 T(N)=O(F(N))。
- 计算两步法：① 找与 n 有关的循环、数循环体执行次数得 T(n)；② 取最高次项并去掉系数。无 n 相关语句则为 O(1)。
- 双重无关联循环 ∑∑1=n2⇒O(n2)；关联循环（j<i）执行 n(n−1)/2 次仍为 O(n2)。
- 求和定理：顺序两段 T1+T2=O(MAX(f(n),g(n)))；求积定理：嵌套 T1×T2=O(f(n)×g(n))；关联循环可按内层最坏 O(n) 用求积得 O(n2)。
- 常见量阶（效率高→低）：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nN)；常量级到平方级为易性算法，立方阶及以上为顽性算法。
- O(f(n)) 只给量阶不给精确值；分最好/最坏/平均三种情况，一般取最坏情况。
- 查找对比：有序序列二分查找最多 log2N+1 次，顺序查找最坏 N 次；N=10000 时后者超前者 1000 倍。
- 空间消耗三方面：程序本身、待处理数据、额外辅助空间；前两者不可避免，设计算法主要关注辅助空间。
- 空间复杂度 S(n)=O(f(n))：n 趋于无穷时辅助空间的量阶。逆置用辅助数组 b 为 O(n)；原地用临时变量 t 为 O(1)。
- 无临时变量交换两数：加减法、乘除法、三句异或法、Python 的 a,b=b,a；加减/乘除有溢出或除零限制，异或只适用于整数，C/C++ 不建议使用链式
a^=b^=a^=b。
- 内存足够大时优先时间效率；仅当时间复杂度一致时才比较空间复杂度。
- 空间换时间：哈希算法（输入经散列得键值；为降低哈希冲突需保留大量空位）；时间换空间：操作系统用硬盘充当内存（swap），换回数据耗时导致卡顿。
- 四个研究方面：逻辑结构及基本操作（完全脱离计算机分析，给出伪代码描述的抽象数据类型）→ 物理结构（顺序/链式）→ 基本操作实现（算法及时间/空间复杂度比较）→ 典型应用。