zq—算法基础：时空复杂度（1）
算法基础之时空复杂度（1）算法复杂度的定义
复杂度分析
算法复杂度是衡量算法的重要工具，用于描述算法的资源消耗与输入规模的关系
时间复杂度vs空间复杂度
“时间”vs“存储空间”
预测算法性能，比较不同算法vs评估内存使用，优化存储效率
重要性
复杂度分析帮助我们选择合适的算法，特别是在处理大规模数据时
渐进分析
关注点：
当数据规模n趋于无穷大时的增长趋势
三种情况：
[*]最好情况
[*]平均情况
[*]最坏情况
- 通常分析最坏情况：保证性能下界
数学符号
三种表示法
大 O 的性质
重要性质
[*]忽略常数系数：O(3n)=O(n)
[*]忽略低阶项：\(O(n^2+n)=O(n^2)\)
[*]传递性：如果f(n)=O(g(n))且g(n)=O(h(n)),f(n)=O(h(n))
eg.\(T(n)=5n^2+3n+10\)
\(=O(n^2+n+1)\)
\(=O(n^2)\)
算法复杂度层次图
算法竞赛中的复杂度要求
重要原则
[*]算法竞赛中，一般每题的复杂度上限为\(2\times10^7\)次操作
[*]除特殊情况外，空间复杂度要求一般与时间复杂度要求一致
[*]选择算法时，要根据题目给出的数据范围来判断可行的时间复杂度
常数时间复杂度 O(1)
特点：
执行时间与输入规模无关
典型事例
[*]变量赋值
[*]访问列表、字典某个索引的元素
[*]列表尾部的 append、pop 操作
代码示例
点击查看代码def constant_time(lst);
return lst典型数据范围
\(n \leq 10^{18} （或10^9）\)
对数时间复杂度 O(log n)
特点：
每次操作将问题规模按比例减小（通常是减半）
典型事例
[*]一个循环，其循环变量以乘法或除法方法式逼近边界
代码示例
点击查看代码def logarithmic_time(n): i=1 while i
页:
[1]