算法基础之时空复杂度（1）

张开发
• 2026/4/10 5:29:12 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

算法基础之时空复杂度（1）
算法复杂度是衡量算法的重要工具用于描述算法的资源消耗与输入规模的关系时间复杂度vs空间复杂度“时间”vs“存储空间”预测算法性能比较不同算法vs评估内存使用优化存储效率重要性复杂度分析帮助我们选择合适的算法特别是在处理大规模数据时渐进分析关注点当数据规模n趋于无穷大时的增长趋势三种情况最好情况平均情况最坏情况- 通常分析最坏情况保证性能下界数学符号三种表示法大 O 的性质重要性质忽略常数系数O(3n)O(n)忽略低阶项O(n2n)O(n2)(2)(2)传递性如果f(n)O(g(n))且g(n)O(h(n)),f(n)O(h(n))eg.T(n)5n23n10()52310O(n2n1)(21)O(n2)(2)算法复杂度层次图算法竞赛中的复杂度要求重要原则算法竞赛中一般每题的复杂度上限为2×1072×107次操作除特殊情况外空间复杂度要求一般与时间复杂度要求一致选择算法时要根据题目给出的数据范围来判断可行的时间复杂度常数时间复杂度 O(1)特点执行时间与输入规模无关典型事例变量赋值访问列表、字典某个索引的元素列表尾部的 append、pop 操作代码示例点击查看代码典型数据范围n≤1018或109≤1018或109对数时间复杂度 O(log n)特点每次操作将问题规模按比例减小通常是减半典型事例一个循环其循环变量以乘法或除法方法式逼近边界代码示例点击查看代码典型数据范围n≤1018或109≤1018或109线性时间复杂度 O(n)特点执行时间与输入规模成正比典型事例遍历列表列表的pop(O)操作代码示例点击查看代码典型数据范围n≤106或105,2×106≤106或105,2×106线性对数时间复杂度 O(nlog n)特点通常是将一个 O(log n)的操作重复n次或一个 O(n)的操作重复log n次典型事例许多高效算法的标志性复杂度调和级数与线性结合n×(11213...1n)×(11213...1)代码示例点击查看代码典型数据范围n≤2×105或105≤2×105或105n√x时间复杂度 O(n1.5)(1.5)特点复杂度介于线性对数和平方之间通常出现在较复杂的分块或数学算法中典型事例分块算法某些数论算法代码示例点击查看代码典型数据范围n≤104≤104平方时间复杂度 O(n2)(2)特点二重嵌套循环的典型复杂度典型事例二重嵌套循环代码示例点击查看代码典型数据范围n≤5000≤5000立方时间复杂度 O(n3)(3)特点三重嵌套循环的典型复杂度典型事例三重嵌套循环代码示例点击查看代码典型数据范围n≤300≤300指数时间复杂度 O(2n)(2)特点问题规模每增加1执行时间翻倍增长极快。描述常出现于解决一个问题的所有可能自己相关的问题中。典型数据范围n≤20≤20阶乘时间复杂度 O(n!)特点

更多文章