1. 时间复杂度求解考点复盘#

考研408中时间复杂度是数据结构开篇必考的基础核心考点，核心考察渐进时间复杂度的大O表示法规则与常见场景计算：

• 计算规则：只保留最高阶项，忽略常数项、低阶项与最高阶项系数，例如3n²+5n+8的复杂度为O(n²)，2nlog₂n的复杂度为O(nlogn)。
• 常见复杂度阶数排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2^n) < O(n!)。
• 常考场景推导： 单层循环执行n次，复杂度为O(n)；两层嵌套循环复杂度为O(n²)；步长为倍数的循环（如for(i=1; i<=n; i*=2)）复杂度为O(logn)；递归场景如斐波那契朴素递归复杂度为O(2^n)，二分查找递归实现复杂度为O(logn)。

2. 顺序表基础操作考点复盘#

顺序表是线性表的主流存储结构，是408代码题、简答题的高频考点：

• 两种实现形式：静态分配（使用固定长度数组，无法动态扩容）和动态分配（通过malloc申请堆内存，支持容量扩容）。
• 核心基础操作考点：

1. 初始化：静态分配直接初始化数组与表长；动态分配需要申请指定大小的内存空间，初始化表长与当前容量。
2. 按位置插入：需要先校验表是否已满、插入位置合法性（严版教材合法范围为1<=i<=L.length+1），插入时需从表尾到插入位置依次后移元素避免数据覆盖，最后更新表长。
3. 按位置删除：校验删除位置合法性，将删除位置后的所有元素依次前移覆盖，最后更新表长。
4. 查找操作：按位查找直接返回对应下标元素，按值查找遍历顺序表匹配目标元素并返回下标。

• 易错提醒：插入操作必须从后往前移动元素，否则会提前覆盖未处理的数据；动态顺序表扩容通常采用翻倍扩容策略，减少频繁内存申请的开销。