当前位置：首页 > news >正文

2026《数据结构》考研复习笔记四（绪论）

news 来源：原创 2025/6/17 23:42:35

绪论

前言
时间复杂度分析

前言

由于先前笔者花费约一周时间将王道《数据结构》知识点大致过了一遍，圈画下来疑难知识点，有了大致的知识框架，现在的任务就是将知识点逐个理解透彻，并将leetcode刷题与课后刷题相结合。因此此后的过程中，整理的笔记不仅包含课本知识点，还包含经典课后题讲解（主要是笔者认为重要的）以及leetcode代码（用于深入理解重要知识点）。综上，复习思路为：大致过一遍知识点有个系统框架->写代码深入理解->刷题适应考试模式

经复习，我将本书大致分为四部分——第一章：绪论（主要是算法效率的度量），第二章+第三章+第四章：线性结构（包括数组、链表、栈、队列以及串），第五章+第六章：非线性结构（包括树、图），第七章+第八章：实际应用（包括顺序查找、树形查找、散列查找以及各种排序算法）。

本篇文章为第一部分，除了一些零散的概念性知识，只有一个较为重要的考点——时间复杂度分析。记住结论即可，有兴趣的同学可以自行推理（本来是想写一下的，但是太费时间了，而且估计看的人不多，所以自行推理吧）

时间复杂度分析

我们将循环分为两种类型——等差递增和等比递增（递减可以转化为递增）。常见形式如：

等差递增：for(int i=0;i<n;i++)
等比递增：for(int i=1;i<n;i*=2)

为了找出一般规律，我们接下来探究等差递增和等比递增的一般形式：

等差递增：for(int i=a₀;i<n;i+=d)。其中a₀为首项，d为等差
等比递增：for(int i=a₀;i<n;i*=q)。其中a₀为首项，q为等比

一、单层for循环

类型	时间复杂度
等差for(int i=a~0~;i< n;i+=d)	O(n)
等比for(int i=a~0~;i< n;i*=q)	O(logn)

推导过程：
（假设运行次数为t，即最后一次运行i=a_t）
1.对于等差递增，有n-d<=a_t<n，即n-d<=a₀+t * d<n，推导出(n-d-a₀)/d<=t<(n-a₀)/d，忽略常数，有时间复杂度为O(n)
2.对于等比递增，有n/q<=a_t<n，即n/q<=a₀ * q^t<n，推导出log_q(n/(q * a₀))<=t<log_q(n/a₀)，经过换底公式后忽略常数，有时间复杂度为O(logn)

二、双层for循环
首先将双层for循环分为两种类型：

上下变量无关：上层递增变量与下层递增变量没有直接关系。如：
for(int i=0;i<n;i++) for(int j=0;j<m;j++)
上下变量有关：下层递增变量依赖于上层递增变量。如：
for(int i=0;i<n;i++) for(int j=0;j<i;j++)//j的初始值为i
同时我们将递增类型分为两种类型：
加法（等差递增）：for(int i=a₀;i<n;i+=d)。其中a₀为首项，d为等差
乘法（等比递增）：for(int i=a₀;i<n;i*=q)。其中a₀为首项，q为等比

假设两层for循环的判断条件都是n（即i<n、j<n）：

上下变量无关

第一层for循环	第二层for循环	时间复杂度
乘法	乘法	O(log²n)
乘法	加法	O(nlogn)
加法	乘法	O(nlogn)
加法	加法	O(n²)

上下变量有关

第一层for循环	第二层for循环	时间复杂度
乘法	乘法	O(log²n)
乘法	加法	O(n)
加法	乘法	O(nlogn)
加法	加法	O(n²)

仅有先乘后加的时候有区别，前者为O(nlogn)后者为O(n)——参见2022统考真题，其中便考察了这个知识点

注意：对于上下变量有关，第一层为加法，第二层为乘法的时候，最终的时间复杂度为O(logn!)，根据斯特林公式，n!≈√(2nπ)(n/e)ⁿ，取对数后化简为nlogn

至于上下for循环参数不一致，在此也不再讨论（出题概率较低）

绪论

前言

时间复杂度分析

相关文章：