简介面向CSP-J/SNOIP初赛选手的集训课件以程序设计基础知识中的算法与数据结构为主线适合需要系统备赛、快速搭建知识框架的考生。课件系统梳理算法定义、大O表示法、时间复杂度与空间复杂度推导、算法评价中的时间空间权衡并覆盖冒泡、选择、插入、归并等排序算法以及线性表、树与二叉树、图论基础同时穿插迭代法、递推方程求解技巧和近年NOIP真题选讲有助于熟悉初赛选择题与综合题的命题思路。资源打包为1个PDF文件体积约3.74MB便于打印或离线学习。目前已有878人学习下载。内容以章节化形式组织从常见复杂度量级对比到双向链表复杂度分析均有详细示例适合考前集中复习对需要夯实算法基础、提升笔试题得分率的选手尤其实用。1. 初赛集训绕不开的第一关算法复杂度与数据结构基础想走通 CSP-J/S、NOIP 这条信息学奥赛路初赛是所有人都要过的第一道闸门。而初赛里最劝退人的不是代码量反而是那堆看起来像数学题又像脑筋急转弯的算法复杂度题。这份初赛集训配套课件PART2 聚焦的正是 CSP-J1/S1 初赛中反复出现的「程序设计基础知识」——算法定义、大O表示法、时间复杂度推导、递推方程求解、排序算法复杂度、线性表与双向链表。它不教你写完整程序而是把初赛笔试里必然出现的复杂度题拆开讲透。适合两类人一类是刚开始备赛、连大O都没弄明白的新手另一类是刷题到瓶颈、想靠真题反推考点的参赛者。把这个资源啃完再遇到“某某算法的时间复杂度是多少”这类题你就不会再靠蒙了。2. 大O表示法与算法评价从“跑一遍计时”到“推导一切”的思维转变2.1 为什么不能靠运行计时来评价算法很多人拿到一段算法代码第一反应是“把它跑一遍看看花了几毫秒”。这个思路本身没毛病但一旦放在信息学奥赛的初赛场景里就完全行不通了。原因有三层。第一运行环境不可控。同一段代码在性能高的评测机上可能跑出 0.01 秒换到老旧笔记本上可能变成 0.5 秒你没法拿这个结果去评价算法本身的优劣。第二数据规模直接影响耗时。数据量从 100 涨到 10000运行时间不是线性涨可能是平方级甚至指数级地涨你测出来的“耗时”只是某个特定规模下的快照不具备普适性。第三也是初赛最现实的一点——笔试环节你根本没法运行代码必须在纸面上完成推导。所以行业内才形成了一套通用的评价体系用「时间复杂度」和「空间复杂度」两个维度去描述算法效率。时间复杂度描述的是执行算法消耗的时间随数据规模增长的变化趋势空间复杂度描述的是占用内存随数据规模增长的变化趋势。两者都是用大O符号表示即 T(n) O(f(n))。这里的 f(n) 表示每行代码执行次数之和O 表示正比例关系全称是“算法的渐进时间复杂度”。注意这个“渐进”——它关心的是 n 趋向无穷大时算法表现的趋势而不是某个具体 n 值下的精确耗时。2.2 大O推导的三条规则与时间复杂度公式大O表示法的推导有一套固定规则掌握之后几乎所有复杂度题都能标准化处理。这套规则在信息学奥赛初赛里属于必须背下来的基本功我直接按课件里的内容拆开讲。规则一用常数 1 取代运行时间中的所有加法常数。意思是如果你的算法执行次数表达式里有一堆常量项比如 3、5、100统统看作 1。因为当 n 足够大时这些常数对增长趋势的影响可以忽略不计。规则二在修改后的运行次数函数中只保留最高阶项。比如你算出来一个算法的执行次数是 3n² 2n 1保留最高阶项 3n²去掉 2n 和 1。规则三如果最高阶项存在且不是 1则去除与这个项相乘的常数。3n² 去掉系数 3变成 n²。把这三条规则合起来得到的表达式就是大O阶。举个课件里的例子for(i1; in; i) // 循环 n 次 { j i; // n 次 j; // n 次 }这里 for 循环、赋值、自增各执行 n 次总共约 3n 次操作。根据规则三去掉最高阶项 n 前面的系数 3最终时间复杂度就是 O(n)。这就是为什么这段代码最终被判定为线性阶——它消耗的时间随 n 线性增长。理解了这套推导规则你就能明白为什么有些代码看起来很长实际复杂度却是 O(1)int i 1; int j 2; i; j; int m i j;这段代码无论写多少行只要没有循环、递归等复杂结构执行次数就是固定的不随任何变量增长而变化。哪怕它有几十万行只要都是顺序执行的简单语句大O表示法依然用 O(1) 来描述。这个结论在初赛选择题里经常出现专门用来考察你对大O本质的理解。2.3 常见复杂度量级从 O(1) 到 O(2ⁿ) 要能按序排出来课件里列了 8 个常见的时间复杂度量级从上到下依次变大执行效率依次降低。这个顺序必须背到形成条件反射的程度。常数阶 O(1) 是最理想的执行时间与数据规模无关。对数阶 O(logN) 次之典型特征是循环变量不断倍增。线性阶 O(n) 是单层循环的标配。线性对数阶 O(nlogN) 出现在快速排序、归并排序这类分治算法里。平方阶 O(n²) 常见于双重循环。再往上还有立方阶 O(n³)、K 次方阶 O(n^k)以及最可怕的指数阶 O(2ⁿ)。初赛题里如果出现指数阶复杂度的算法基本可以直接判死刑因为 n 稍微大一点就跑不动了。对数阶是最容易让人犯迷糊的我展开说一下。课件里有这段示例int i 1; while(i n) { i i * 2; }这个 while 循环里每次 i 都乘以 2。假设循环 x 次后 i 大于等于 n循环退出那么 2 的 x 次方等于 nx log₂n。也就是说循环执行了 log₂n 次时间复杂度就是 O(logn)。这种“变量倍增、循环次数对数化”的模式在初赛里反复出现看到循环变量指数增长就要条件反射想到对数阶。2.4 空间复杂度鱼和熊掌的取舍逻辑初赛对空间复杂度的考察通常不像时间复杂度那么深但基本概念和计算逻辑你一定要懂。空间复杂度同样用大O表示法描述衡量的是算法执行过程中占用的内存空间随数据规模增长的变化趋势。这里最典型的考点是时间与空间的权衡。例如递归算法的递归调用栈深度如果递归深度是 n那么隐式的栈空间复杂度就是 O(n)。再如用数组实现链表功能时虽然额外开了一个指针数组占用 O(n) 空间但换来了 O(1) 的插入删除操作。课件里特别提到“时间和空间是鱼和熊掌不可兼得”这句话在初赛的判断题和选择题里经常以各种变体出现。记住一个结论算法优化一般是在时间优先的前提下尽量控制空间占用如果空间限制很紧就只能牺牲时间换空间。具体怎么权衡取决于题目给出的运行时间和内存上限。3. 递推方程与迭代法初赛复杂度真题的推导路径3.1 迭代法求解递推方程的基本框架初赛里有一类高频拦路题给出递推关系式比如 T(n) T(n-1) n然后问你时间复杂度是多少。这类题表面看是数学题实际上考察的是用迭代法展开递推方程的能力。这也是这一部分课件重点讲解的内容。迭代法的核心思路很简单把 T(n) 不断往前一层一层展开找到展开后的规律最后整理成关于 n 的封闭表达式。具体操作框架分三步。第一步写出递推关系本身包括初始条件。比如 T(n) T(n-1) nT(0) 1。第二步把 T(n) 用 T(n-1) 的表达式替换再用 T(n-2) 替换 T(n-1)一层层迭代展开。第三步观察展开过程中出现的规律找到通项公式并利用初始条件确定常数值。课件里的例题就是这么解的。T(n) T(n-1) n不断展开T(n-1) T(n-2) (n-1)所以 T(n) T(n-2) (n-1) n。继续展开 T(n-2) T(n-3) (n-2)所以 T(n) T(n-3) (n-2) (n-1) n。一直展开到 T(0)得到 T(n) T(0) 1 2 ... (n-1) n。代入 T(0) 1得到 1 1 2 ... n 1 n(n1)/2。最高阶项是 n²所以时间复杂度为 O(n²)。这套展开路径看起来简单但我见过太多人在这一步翻车。翻车原因通常不是展开不会而是展开到最后不会整理等差数列求和公式记错、最高阶项判断失误、忽略初始条件导致常数项错误。这些坑我放在后面第 5 章的避坑指南里专门讲。3.2 从 T(n)T(n-1)n 看 2015 年普及组第 19 题2015 年 NOIP 普及组第 19 题直接考察了上一个小节的递推方程求解能力。题目是设某算法的计算时间表示为递推关系式 T(n) T(n-1) nn 为正整数及 T(0) 1则该算法的时间复杂度为选项A. O(log n)、B. O(n log n)、C. O(n)、D. O(n²)。如果用前面说的迭代法展开全过程就是T(n) T(n-1) n T(n-2) (n-1) n ... T(0) 1 2 ... n 1 n(n1)/2。最高阶项是 n²选 D。这道题难吗从技术上讲不难但它出现在初赛真题里说明出题人认定“迭代法解递推方程”是参赛者必须掌握的技能。这道题的正确答案是 D也是当年区分度较大的一道题——不少考生凭直觉选 C因为看到 T(n-1)n 里有 n 想当然以为线性阶忽略了累加结果其实是平方量级的。这个错误非常典型根源在于没有真正展开递推只是凭“循环一次加一次”的表面现象直接推断。递推方程的时间复杂度不是看单次递推的增量而是看整个递推展开后的总运算量。单次增量为 n递推 n 次总量自然是 12...n 的量级。3.3 用递推方程识别复杂度陷阱除了 T(n) T(n-1) n 这种基础形式初赛题里递推方程的变体还有不少。最常见的变体是分治型递推比如 T(n) 2T(n/2) O(n)。这种形式出现在归并排序里展开后每一层都是 n 的运算量层数是 log n 层总复杂度是 O(n log n)。如果题目把系数改成 2、把子问题规模改成 n/2你要能意识到这是归并排序类算法的复杂度来源。还有一种变形是 T(n) aT(n/b) f(n) 的一般形式。初赛通常只考最基础的 a2、b2、f(n)n 这种特例但你要能识别出“递归树展开后每层运算量、树的层数、总运算量”这三个维度的关系。方法是先看递推展开后有多少层也就是递归深度再看每一层的总运算量最后二者相乘。对了这里有个容易被忽略的点递推方程里的 T(0) 或 T(1) 的初始值一定要看清楚。不同的初始值只影响常数项不影响最高阶项所以通常不改写复杂度结论。但如果题目问的是精确运算次数初始值就变得关键了。4. 排序算法与线性表真题考点背后的复杂度账本4.1 排序算法复杂度总表与记忆方法排序算法复杂度在初赛中几乎是必考考点。课件里给了一张排序算法复杂度表我在这基础上整理出一套记忆和使用方法。表里要记住的信息分三列最好情况、平均情况、最坏情况的时间复杂度以及是否稳定。快速排序和归并排序的平均时间复杂度都是 O(n log n)但快速排序在最坏情况下会退化到 O(n²)而归并排序在任何情况下都是 O(n log n)。插入排序在最好情况下输入基本有序是 O(n)平均和最坏是 O(n²)。冒泡排序和选择排序平均和最坏都是 O(n²)。基数排序属于非比较排序平均时间复杂度是 O(d(nr))在元素位数有限时接近线性。记忆方面我一般推荐两个锚点平均复杂度为 O(n log n) 的排序算法只有快速排序、归并排序、堆排序平均复杂度为 O(n²) 的是插入排序、冒泡排序、选择排序。考试里只要问“平均时间复杂度是 O(n log n) 的是哪个”答案就在前三者里选再根据“是否稳定”“是否原地排序”等附加条件排除。课件里正好有 2013 年普及组的真题用到了这个知识点。4.2 2013 年普及组第 14 题O(n log n) 选择题的排除法2013 年 NOIP 普及组第 14 题题干是“的平均时间复杂度为 O(n log n)其中 n 是待排序的元素个数”四个选项分别是 A. 快速排序、B. 插入排序、C. 冒泡排序、D. 基数排序。如果你掌握了那张复杂度总表这道题的答案已经出来了A。插入排序和冒泡排序平均都是 O(n²)基数排序并不是 O(n log n)——它由位数 d 和基数 r 决定。但为了保险起见做题时我还习惯把四种排序的最坏情况也过一遍快速排序最坏 O(n²)插入排序和冒泡排序最坏 O(n²)基数排序只要位数固定就是 O(dn)。如果题目把“平均”改成“最坏”答案就不一样了这点审题时要特别注意。另外这道题还提醒我要额外记忆快速排序的特征它对数据分布敏感平均情况能到 O(n log n)但碰到已经有序或者完全逆序的数据会退化到 O(n²)。这也是为什么很多工程排序实现会在数据量小或接近有序时切换到插入排序——插入排序在近有序数据表现极好最好情况 O(n)。4.3 线性表选型数组、单链表、双向链表的 CRUD 复杂度线性表是初赛数据结构的重点考察内容形式上分数组和链表两大类。数组的特点是连续存储按下标随机访问任意元素的时间复杂度是 O(1)但插入和删除操作需要移动大量元素平均 O(n)。链表的特点是节点分散存储通过指针串联插入和删除在已知位置的情况下只要 O(1)但按位置或关键字查找需要从头遍历平均 O(n)。单链表最尴尬的地方是要在某个节点之前插入新节点或者删除某个节点虽然实际操作是改指针但必须先从头部遍历找到该节点的前驱节点。这个查找过程是 O(n) 的导致单链表的插入删除操作表面是 O(1)实际从用户角度看还是 O(n)。这也是为什么需要双向链表——它在节点结构里同时保存了前驱和后继指针可以直接定位到前驱节点无需遍历。课件里在讲线性表时特别点出了双向链表的复杂度特征删除给定节点和插入操作的时间复杂度是 O(1)查询操作是 O(n)。这个结论看着简单但初赛选择题里经常挖坑我后面会专门讲。4.4 双向链表删除、插入操作的时间复杂度辨析为什么双向链表的删除和插入能做到 O(1)因为节点结构里既有 next 指针指向后继又有 prev 指向前驱。以删除给定节点 p 为例操作只需要两步——让 p-prev 的 next 指向 p-next让 p-next 的 prev 指向 p-prev然后释放 p。整个过程不涉及任何循环从头到尾是常数时间。插入操作同理。在节点 p 后面插入新节点 q只需要修改 q.prev 指向 p、q.next 指向 p.next、p.next.prev 指向 q、p.next 指向 q。不管链表多长这个操作都不需要遍历所以是 O(1)。但注意这里有个前提条件你手里已经拿到了要操作的位置指针。如果是“在链表中查找某个关键字为 k 的元素”这种操作无论单链表还是双向链表最坏都要 O(n)。2011 年 NOIP 普及组第 13 题考的就是这个点在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素最快情况下运行的时间复杂度是多少。答案是 O(n)选项 C。这道题想表达的核心结论是双向链表的优势在于已知节点位置时的删除、插入操作是 O(1)但查找关键字仍需要遍历最坏 O(n)。它的劣势也很明显每个节点多了一个指针域空间开销更大维护成本也更高。课件里原话是“若从工程角度考量则其维护性和可读性都更低”。所以做题时见到“双向链表的时间复杂度”相关选择题先区分题目问的是“在已知位置操作”还是“按值查找”这一步区分对了答案基本就出来了。5. 复杂度与数据结构题的高频坑避坑指南5.1 坑一把单次操作的复杂度当成整体复杂度现象题目给出 T(n) T(n-1) n有些考生直接看到“每次加 n”就认为复杂度是 O(n)踩中了 2015 年普及组第 19 题的陷阱。原因只看了单次递推的增量没有把整个递推过程展开。单次增量是 n但递推 n 次之后总运算量是 1 加到 n 的累加和量级是 n²。解决碰到递推方程强制自己展开三步再下结论。T(n) T(n-1) n第一步展开成 T(n-2) (n-1) n第二步展开成 T(n-3) (n-2) (n-1) n第三步观察累加规律。展开到等差数列出现时就该意识到要用求和公式而不是乘法公式。这个方法对初赛里绝大多数递推方程题都适用。5.2 坑二对循环次数想当然没看清变量的变化方式现象看到while(in) { i i * 2; }这类代码有人以为循环执行 n 次判定为 O(n)。原因没有关注循环变量 i 的变化方式。i 每次乘以 2循环次数不是 n 而是 log₂n。这是大O复杂度题里最经典的一个盲区也是“对数阶 O(logN)”最常出现的切入点。解决分析任何循环的时间复杂度先问自己三个问题循环变量初始值是多少每次迭代循环变量怎么变循环退出条件是什么只要循环变量是指数增长乘 2、乘 3、平方复杂度就是对数量级只有循环变量线性变化加 1、减 1复杂度才是线性量级。做题时把这套检查流程走一遍基本能避开这个坑。5.3 坑三把链表已知位置操作和按值查找混为一谈现象看到“双向链表删除操作时间复杂度”答 O(n)看到“双向链表查询关键字”答 O(1)。两个答案正好反了。原因没有区分题目指定的是“已知节点指针”还是“按关键字找节点”。双向链表删除给定节点是 O(1)但按关键字查找必须遍历链表最坏情况 O(n)。课件里的 2011 年普及组第 13 题考的就是“查询是否存在关键字为 k 的元素”考察重点恰恰是后者。解决做题前先圈出题干的动词。出现“删除”“插入”“给定节点”等字样优先往“已知位置操作”上想答案是 O(1)出现“查询”“查找”“是否存在”等字样老老实实选 O(n)。另外如果题干没有明确说“给定位置”那所有操作都要考虑从头部开始的查找成本。5.4 坑四排序算法复杂度只记平均不记最坏现象题目问“快速排序在最坏情况下的时间复杂度”有人直接回答 O(n log n)因为只记住了平均情况。原因很多初学者背复杂度总表时只背一排平均情况忽略了最坏情况的退化。快速排序在最坏情况下比如每次划分都极端不平衡会退化到 O(n²)而归并排序最坏仍然是 O(n log n)这是两者的重要区别。解决整理排序算法时表格至少列三列最好、平均、最坏。快排的标法是“O(n log n) / O(n log n) / O(n²)”归并排序是“O(n log n) / O(n log n) / O(n log n)”。考试遇到“最坏情况仍然高效”的说法优先考虑归并遇到“平均高效但最坏退化”优先考虑快速排序。这两个结论在初赛选择题里出现的频率非常高。6. 考前实战把复杂度推断做成“肌肉记忆”这里分享一个我自己的训练方法适用对象是考前两到三周、需要对复杂度题形成条件反射的参赛者。方法很简单在每次刷真题的选择题部分时额外准备一张空白纸把每道涉及复杂度的题都强制展开完整推导在题号边上写下关键步骤而不是只写出最后答案。我给自己定的标准有三个一是递推方程必展开到第三层再归纳通项二是循环类代码必先写出循环变量的变化方式和退出条件三是排序算法复杂度遇到任何题不管是平均还是最坏都把三者全写一遍。比如 2013 年那道排序题正确答案是快速排序我会在草稿纸上写“O(n log n) 平均快排、归并、堆排O(n²) 平均插入、冒泡、选择”——把这行话写在题旁边比只选一个 A 有效得多。这个方法费不了多少时间但能让你在考场里遇到类似题时直接调用写过的推导模板而不是临场去猜。还有个小习惯值得养成每次分析完一个复杂度顺手把对应的数据结构操作类型也一并写出来。比如看到“双向链表删除给定节点”写“O(1)因为直接操作前驱后继指针”看到“双向链表按值查询”写“O(n)因为需要遍历”。把知识点和场景绑定在一起记忆比单独背知识点牢靠得多。这套流程走习惯之后初赛里的复杂度选择题基本就是送分题了。我也犯过把链表的查询和删除搞混的低级错误从那以后我每次做链表复杂度题都强制自己先写一句“已知位置还是按值查找”再往下判断。希望帮到你。本文还有配套的精品资源点击获取