zfk_蓝桥杯C++学习_递归及时空复杂度

递归

一、递归的介绍
概念： 递归是指函数直接或间接调用自身的过程。

解释递归的两个关键要素：
1.基本情况（递归终止条件）：递归函数中的一个条件，当满足该条件时，递归终止，避免无限递归。可以理解为直接解决极小规模问题的发法。
2.递归表达式（递归调用）：递归函数中的语句，用于解决规模更小的子问题，再将子问题的答案合并成为当前问题的答案。

二、递归如何实现
递归函数的基本结构如下：

返回类型函数名(参数列表）
{//基本情况（递归终止条件）if(满足终止条件）	{//返回终止条件下的结果}  //递归表达式（递归调用）else{//将问题分解为规模更小的子问题//使用递归调用解决子问题//返回子问题的结果}
}

实现过程：
1.将大问题分解为规模更小的子问题。
2.使用递归调用解决每个子问题。
3.通过递归终止条件来结束递归。

设计时需注意的细节：
1.确保递归一定能到递归出口，避免无限递归，这可能导致TLE（超时）、MLE（超内存）或RE（运行错误）。
2.考虑边界条件，有时候递归出口不止一个。
3.避免不必要的重复计算，尽可能优化递归函数的性能(例如使用记忆化)。

三、递归和循环的比较
1.递归的特点：
直观、简洁，易于理解和实现。
适用于问题的规模可以通过递归调用不断减小的情况。
可以处理复杂的数据结构和算法，如树和图的遍历。
存在栈溢出风险（栈空间一般只有8MB，所以递归层数不宜过深，一般不超过1e6层)。

2.循环的特点：
直接控制流程，效率较高。
适用于问题的规模没有明显的缩减，或者需要特定的迭代次数。
适合处理大部分的动态规划问题。
在部分情况下，递归和循环可以相互转化。

时空复杂度

一、时间复杂度
1）时间复杂度是衡量算法执行时间随输入规模增长的增长率。
2）通过分析算法中基本操作的执行次数来确定时间复杂度。
3）常见的时间复杂度包括：常数时间O(1)、线性时间O(n)、对数时间O(logn)、平方时间O(n^2)等。
4）在计算的时候我们关注的是复杂度的数量级，并不要求严格的表达式。

二、空间复杂度
1）空间复杂度是衡量算法执行过程中所需的存储空间随输入规模增长的增长率。
2）通过分析算法中所使用的额外存储空间的大小来确定空间复杂度。
3）常见的空间复杂度包括：常数空间O(1)、线性空间O(n)、对数空间O(logn)、平方空间 O(n^2)等。

三、分析技巧
1.理解基本操作：基本操作可以是算术运算（加法、乘法、位运算等）、比较操作、赋值操作等。
2.关注循环结构：循环是算法中常见的结构，它的执行次数对于时间复杂度的分析至关重要。
3.递归算法：递归算法的时间和空间复杂度分析相对复杂。需要确定递归的深度以及每个递归调用的时间和空间开销。
4.最坏情况分析：对于时间复杂度的分析，通常考虑最坏情况下的执行时间。要考虑输入数据使得算法执行时间达到最大值的情况。
5.善用结论：某些常见算法的时间和空间复杂度已经被广泛研究和证明。可以利用这些已知结果来分析算法的复杂度。

四、什么是限制
1.时间限制到底是什么意思？
比赛中，每道题都有时间限制：
简单题：1秒内完成。
中等题：2秒内完成。
困难题：可能给你5秒。

关键问题：1秒能做多少事情？
现代计算机1秒大约能执行 10^8 次简单操作（加减乘除、比较等）
如果你的算法需要 10^9 次操作，就会超过1秒的限制 → TLE ❌
如果只需要 10^7 次操作，就能轻松通过 → AC ✅

2.空间限制是什么？
每道题还会限制你能用多少内存，比如：
64MB、128MB、256MB、512MB等
快速换算：
1个 int = 4字节
100万个 int = 4MB
如果你开了一个 int a[100000000] (1亿个int)，就需要400MB
如果题目只给256MB，你就会得到"Memory Limit Exceeded (MLE)" ❌
五、复杂度表示方法
在竞赛中，几乎只用大O记号，写作 O(f(n))。
通俗理解：
n 是数据规模（比如数组长度、循环次数等）。
O(f(n)) 表示当 n 很大时，算法大概需要执行 f(n) 次操作。
举个例子：
如果算法是 O(n^2)，数据规模 n=1000
那么大概需要 1000²⁼¹⁰6 次操作
10^6<108，所以1秒内能完成 ✅

六、见到题目如何快速估算复杂度
Step 1：看数据范围
n≤10 → 什么算法都行，甚至暴搜
n≤100 → O(n^3)算法OK
n≤1000 → O(n^2)算法OK
n≤10^5 → 需要O(nlog⁡n)或更优算法
n≤10^6 → 需要O(n)或更优算法

Step 2：看时间限制
1秒 → 算法操作次数应该 ≤ 10^8
2秒 → 算法操作次数应该 ≤ 2×10^8

Step 3：结合起来判断 例如：n=10^5，时间限制1秒
O(n²⁾⁼¹⁰10 → 超时❌
O(nlog⁡n)=10^{5×17≈1.7×10}6 → 通过✅

附1.常见复杂度排行榜（从快到慢）

复杂度	名称	n=10^3时的操作次数	n=10^6时的操作次数	评价
O(1)	常数	1	1	超快⚡
O(log⁡n)	对数	~10	~20	很快🚀
O(n)	线性	10^3	10^6	快👍
O(nlog⁡n)	线性对数	~10^4	~2×10^7	还行😐
O(n^2)	平方	10^6	10^12	慢😞
O(n^3)	立方	10^9	10^18	很慢💀
O(2^n)	指数	2^1000	天文数字	超慢☠️

附2.常见算法的复杂度速查表

算法类型	时间复杂度	空间复杂度	适用数据规模
线性搜索	O(n)	O(1)	n≤10^6
二分搜索	O(log⁡n)	O(1)	任意
冒泡排序	O(n^2)	O(1)	n≤10^3
快速排序	O(nlog⁡n)	O(log⁡n)	n≤10^5
归并排序	O(nlog⁡n)	O(n)	n≤10^5
堆排序	O(nlog⁡n)	O(1)	n≤10^5
计数排序	O(n+k)	O(k)	当k不太大时
DFS/BFS	O(V+E)	O(V)	图论问题
Floyd算法	O(n^3)	O(n^2)	n≤500
Dijkstra	O(Elog⁡V)	O(V)	单源最短路