zq算法时空复杂度分析，有哪些问题？

算法基础之时空复杂度（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[0] 典型数据范围 \(n \leq 10^{18} （或10^9）\) 对数时间复杂度 O(log n) 特点： 每次操作将问题规模按比例减小（通常是减半） 典型事例 一个循环，其循环变量以乘法或除法方法式逼近边界 代码示例 点击查看代码 def logarithmic_time(n): i=1 while i<n: i=i*2 典型数据范围 \(n \leq 10^{18} （或10^9）\) 线性时间复杂度 O(n) 特点： 执行时间与输入规模成正比 典型事例 遍历列表 列表的pop(O)操作 代码示例 点击查看代码 def linear_time(lst): for i in lst: print(i) 典型数据范围 \(n \leq 10^6 （或10^5,2\times10^6）\) 线性对数时间复杂度 O(nlog n) 特点： 通常是将一个 O(log n)的操作重复n次，或一个 O(n)的操作重复log n次 典型事例 许多高效算法的标志性复杂度 调和级数与线性结合：\(n \times(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})\) 代码示例 点击查看代码 def harmonic_example(n): s=0 for i in range(n+1): for j in range (i,n+1,i): s+=1 return s 典型数据范围 \(n \leq 2\times10^5 （或10^5）\) \(n\sqrt{x}\)时间复杂度 \(O(n^{1.5})\) 特点： 复杂度介于线性对数和平方之间，通常出现在较复杂的分块或数学算法中 典型事例 分块算法 某些数论算法 代码示例 点击查看代码 def n_sqrt_nexample(n): for i in range(n): j=0 while j*j<=i: print(i,j) j+=1 典型数据范围 \(n \leq 10^4\) 平方时间复杂度 \(O(n^2)\) 特点： 二重嵌套循环的典型复杂度 典型事例 二重嵌套循环 代码示例 点击查看代码 def square_time(n): for i in range(n): for j in range(n): print(i,j) 典型数据范围 \(n \leq 5000\) 立方时间复杂度 \(O(n^3)\) 特点： 三重嵌套循环的典型复杂度 典型事例 三重嵌套循环 代码示例 点击查看代码 def cubic_time(n): for i in range(n): for j in range(n): for k in range(n): print(i,j,k) 典型数据范围 \(n \leq 300\) 指数时间复杂度