蓝桥杯备赛笔记（二）

这里的笔记是关于蓝桥杯关键知识点的记录，有别于基础语法，很多内容只要求会用就行，无需深入掌握。

前言

持续更新，千里之行始于足下

一、时间复杂度

1.1 时间复杂度⭐

1、时间复杂度是衡量算法执行时间随输入规模增长的增长率。
2、通过分析算法中基本操作的执行次数来确定时间复杂度。
3、常见的时间复杂度包括：常数时间O(1)、线性时间O(n)、对数时间O(log n)、平方时间O(n^2)等。
4、在计算的时候我们关注的是复杂度的数量级，并不要求严格的表达式。
一般我们关注的是最坏时间复杂度，用O(f(n))表示，大多数时候我们仅需估计即可。
一般来说，评测机1秒大约可以跑2e8次运算，我们要尽可能地让我们的程序运算规模的数量级控制在1e8以内。

常数时间例子：10→100ms，10000→100ms，这里常数无论多少都是100ms。
线性时间例子：for循环嵌套for循环的情况下，时间复杂度为O(2n)但由于我们并不要求严格的表达式，所以这里的O(2n)=O(n)即可。

评测机1秒跑的2e8即$2\ast 10^8$,假如此时我们的n=1e4的情况下，O($n^2$)约等于1e8次。
但如果是n=1e5的情况下，O($n^2$)约等于1e10次就超过了运算规模的数量级控制了，此时我们应该用O(nlogn)的算法，约等于3e6。

1.2 空间复杂度

1、空间复杂度是衡量算法执行过程中所需的存储空间随输入规模增长的增长率(vector)。
2、通过分析算法中所使用的额外存储空间的大小来确定空间复杂度。(全局大数组)
3、常见的空间复杂度包括：常数空间O(1)、线性空间O(n)、对数空间O(log n)、平方空间O($n^2$)等。
一般我们关注的是最坏空间复杂度，用O(f(n))表示，大多数时候程序占用的空间一般可以根据开的数组大小精确算出，但也存在需要估算的情况。题目一般不会卡空间，一般是卡时间。
举个例子：假如题目限制128MB，1int = 32bit = 4Bytes。128MB = 32 * 2^20int = 3e7int。

1.3 分析技巧

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

总结