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 操作
  

代码示例

点击查看代码

1. def constant_time(lst);
2.     return lst[0]

复制代码

典型数据范围

\(n \leq 10^{18} （或10^9）\)

对数时间复杂度 O(log n)

特点：

每次操作将问题规模按比例减小（通常是减半）
典型事例

• 一个循环，其循环变量以乘法或除法方法式逼近边界
  

代码示例

点击查看代码[code]def logarithmic_time(n):    i=1    while i