考点01：逻辑结构与物理结构（低频）

要点

---

一、逻辑结构

• 元素之间的逻辑关系称为逻辑结构。数据元素之间的逻辑结构有以下4种基本类型。

1. 集合结构：数据元素之间没有任何特殊关系（顺序/层次或连接），它们仅仅是“同属于一个集合”。
2. 线性结构：数据元素按照一定的顺序排列，每个元素（除了第一个和最后一个）都有一个前驱和后继。
3. 树形结构：数据元素之间存在一对多的层次关系。有一个唯一的根结点，其他结点分为若干层级。除根结点无父结点外，其余结点有唯一父结点；每个结点可有零个或多个子结点。
4. 图形结构或网状结构：数据元素之间存在多对多的关系。数据元素可以用结点表示，关系可以用边表示。图可以是有向的（有向图）或无向的（无向图）。

类型	关系类型	典型数据结构	应用场景
集合结构	无关系	集合	数据分类、松散数据的管理
线性结构	一对一	数组、链表、栈、队列	顺序处理、有序存储的数据
树形结构	一对多	树、二叉树、B树	层次结构、快速查找
图形结构	多对多	图、邻接矩阵、邻接表	网络关系、路径规划

---

二、物理结构

• 物理结构是逻辑结构在计算机内存中的具体存储和实现方式。
• 物理结构的设计重点在于：如何存储数据元素，以及如何表示数据元素之间的逻辑关系。
• 物理结构需要体现逻辑结构的逻辑关系。
• 根据逻辑结构在计算机中的表示和实现方式的不同，物理结构可以分为以下四种类型：

顺序存储结构

项目	内容
定义	将数据元素存放在地址连续的存储单元中。
特点	数据之间的逻辑关系和物理关系是一致的。每个数据元素的存储位置可以通过下标直接计算得到。操作速度快，但可能存在存储空间浪费或扩展困难的问题。
典型结构	数组、顺序表
应用场景	数据大小固定，随机访问需求高

链式存储结构

项目	内容
定义	将数据元素存放在任意存储单元中，存储单元可以是连续的，也可以是不连续的。
特点	数据元素的存储位置不能直接反映逻辑关系。通过指针（存放关联数据元素的地址）来表示数据之间的逻辑关系。插入、删除操作效率高，但随机访问效率低。
典型结构	单链表、双链表、循环链表
应用场景	动态数据存储，插入删除频繁

索引存储结构

项目	内容
定义	在存储结点信息的同时，还建立附加的索引表来标识结点的存储地址。
特点	索引表由若干索引项组成，通过索引号确定结点的存储地址。索引存储增加了额外的存储空间开销，但查找效率较高。
典型结构	数据库索引
应用场景	快速定位数据，查找频繁的场景

散列存储结构

项目	内容
定义	通过哈希函数将数据元素的关键码映射到存储地址，建立数据元素存储位置与关键码之间的对应关系。
特点	查找速度快，操作效率高。可能会出现冲突，需要采用冲突解决策略。
典型结构	哈希表、散列表
应用场景	快速查找，缓存设计，字典存储

考点02：时间复杂度（核心高频考点）

核心定义

算法的时间复杂度，以算法中基本操作的重复执行次数作为度量标准，是问题规模 $n$ 的函数，用于衡量算法运行效率随问题规模扩大的变化趋势。
统一采用大O记法表示，只保留增长最快的最高阶项，忽略常数项、低阶项和系数，默认问题规模 $n$ 足够大。

1. 基础概念（选择题常考辨析）

• 语句频度：一条语句的重复执行次数，是计算时间复杂度的核心依据。
• 时间复杂度：算法所有语句频度之和，默认取最深层循环内的基本操作频度，无需计算所有语句。
• 最好时间复杂度：输入数据为最优情况时，算法的基本操作最少执行次数。
• 最坏时间复杂度：输入数据为最差情况时，算法的基本操作最多执行次数。考研题目无特殊说明，均默认计算最坏时间复杂度。
• 平均时间复杂度：所有可能的输入数据等概率出现时，算法基本操作的平均执行次数。

2. 计算规则（必考核心）

1. 只保留最高阶项，低阶项、常数项、最高阶项的系数全部忽略。
2. 加法规则（代码顺序执行）：总复杂度等于多项中量级最高的一项。
   示例：$T(n)=n^2+3n+5$，时间复杂度为 $O(n^2)$
3. 乘法规则（代码嵌套执行）：嵌套代码的总复杂度等于每层循环复杂度的乘积。
   示例：外层循环 $O(n)$，内层嵌套循环 $O(n)$，总复杂度 $O(n\times n)=O(n^2)$

3. 常见复杂度阶数排序（从小到大）

$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

💡 应试易错点：对数复杂度的底数不影响阶数，任意底数的对数均为同阶，即O(log₂n) = O(log₃n) = O(logn)，考试中统一简写为O(logn)即可。

---

考点03：空间复杂度（高频易错点）

核心定义

算法的空间复杂度，是对算法运行过程中，所需额外辅助存储空间大小的度量，同样采用大O记法表示。

1. 存储空间分类（辨析考点）

算法运行占用的存储空间分为三部分：

1. 指令、常量、变量本身占用的固定空间
2. 输入数据本身占用的存储空间
3. 算法执行过程中，额外开辟的辅助存储空间

✅ 考研得分核心：空间复杂度只计算额外的辅助存储空间，输入数据、常量、固定变量的空间不计入复杂度。

2. 常考结论

• 若算法运行所需额外空间为固定常量，与问题规模n无关，空间复杂度为 $O(1)$，称为原地工作（选择题高频考点）。
• 一维数组 $a[n]$，额外空间规模为 $n$，空间复杂度 $O(n)$
• 二维数组 $a[n][m]$，额外空间规模为 $n\times m$，空间复杂度 $O(n\times m)$

---

三、典型例题+分步解析

例题1：基础嵌套循环（最基础考法）

int n = 3;    // 语句①
for(int i = 0; i < n; i++){
    cout << 1;    // 语句②
    for(int j = 0; j < n; j++){
        cout << 2;    // 语句③
    }
}

分步解析：

1. 语句①仅执行 1 次，频度为 1，时间复杂度 $O(1)$
2. 语句②执行 $n$ 次，频度为 $n$，时间复杂度 $O(n)$
3. 语句③为最深层基本操作，嵌套执行 $n\times n$ 次，频度为 $n^2$，时间复杂度 $O(n^2)$
   最终结论：整个算法时间复杂度取最高阶 $O(n^2)$

例题2：顺序独立循环（加法规则考法）

void Func(int N, int M){
     // 第一个独立循环
     for(int k = 0; k < M; ++k)
         ++count; // 语句①
     // 第二个独立循环
     for(int k = 0; k < N ; ++k)
         ++count; // 语句②
}

分步解析：

1. 两个循环顺序执行，无嵌套，适用加法规则
2. 语句①频度 $M$，复杂度 $O(M)$；语句②频度 $N$，复杂度 $O(N)$
3. 总时间复杂度为 $O(N+M)$
   补充结论：若题目限定 $N$ 远大于 $M$，低阶项 $M$ 可忽略，复杂度简化为 $O(N)$

例题3：对数嵌套循环（高频拉分题）

int m = 0, i, j;
for(i=1; i <= n; i *= 2)
   for(j=1; j <= i; j++)
       m++;

分步解析（考试标准步骤）：

1. 外层循环分析：循环变量i初始值为1，每次翻倍，终止条件 $i\le n$
   设循环次数为 $x$，满足 $2^{(x-1)}\le n$，解得 $x=\lfloor lo{g}_{2}n\rfloor +1$，外层复杂度 $O(lo{g}_{2}n)$
2. 内层循环分析：内层循环终止条件依赖外层变量i，每次内层循环执行i次
3. 总频度求和计算：${\sum }_{i=0}^{lo{g}_{2}n}{\sum }_{j=1}^{2^i}1={\sum }_{i=0}^{lo{g}_{2}n}{2}^i=1+2+4+...+2^{lo{g}_{2}n}=2n-1$
   最终结论：总时间复杂度取最高阶 $O(n)$

例题4：非常规终止条件循环（选择题压轴常考）

int func(int n){
    int i = 0, sum = 0;
    while(sum < n)
        sum += ++i;
    return i;
}

分步解析：

1. 循环内基本操作：$sum$ 累加i的值，$i$ 从 1 开始递增
2. 循环 $k$ 次后，$sum$ 的值为等差数列求和：$sum=1+2+3+...+k=k(k+1)/2$
3. 循环终止条件 $sum<n$，代入得：$k(k+1)/2<n$
4. 忽略低阶项和系数，化简得 $k^2\approx 2n$，即 $k=O(\surd n)$
   最终结论：时间复杂度为 $O(\surd n)$（即 $O(n^{(1/2)})$）

---

四、统考考情分析（2009-2026）

考察频次

历年统考中，选择题考察10次，算法设计题必带复杂度分析小问，累计考察12次，属于每年必考、送分必拿的核心考点。

核心考法

1. 选择题：给定一段代码（循环、递归为主），要求分析计算时间/空间复杂度，占2分。
2. 算法设计题：写完代码后，要求分析算法的时间、空间复杂度，固定占2分，是送分点。

应试提醒

本考点难度中等、套路固定，无偏题怪题，掌握上述例题和规则，即可满分拿下所有相关题目。