迭代算法的时间复杂度按增长量级从低到高可分为7大类，不同类型对应不同的迭代场景，以下是结合实际案例的完整梳理：
🔹 常数阶 O(1)
迭代轮数完全固定，和输入规模n无关，单次迭代操作也是常数时间。
典型场景：牛顿迭代法求平方根、梯度下降固定迭代1000轮、WorkBuddy积分领取的固定步骤迭代。
特点：执行效率最高，无论输入规模多大，总耗时几乎不变。
🔹 对数阶 O(log n)
迭代过程中每次都将问题规模缩小为原来的1/2，迭代轮数仅为log₂n级别。
典型场景：二分查找迭代实现、欧几里得求最大公约数迭代算法。
特点：输入规模n极大时，迭代轮数增长也极慢，比如n=100万时，log₂n仅约20轮。
🔹 线性阶 O(n)
迭代轮数和输入规模n成正比，单次迭代为常数时间。
典型场景：数组遍历迭代、批量梯度下降单次遍历全部n个样本、简单线性搜索迭代。
特点：执行效率随n线性增长，是最常见的低复杂度迭代类型。
🔹 线性对数阶 O(n log n)
外层迭代轮数为log n，每轮迭代需要遍历全部n个元素。
典型场景：归并排序迭代实现、快速排序非递归版本、堆排序迭代实现。
特点：性能优于平方阶，是排序类迭代算法的主流高效复杂度。
🔹 平方阶 O(n²)
迭代为两层嵌套循环，外层迭代n轮，内层每轮也迭代n次。
典型场景：冒泡排序迭代、插入排序迭代、朴素数据流分析迭代（CFG节点数为n时，最坏复杂度O(n²)）。
特点：n超过1000后性能会明显下降，仅适合小规模输入场景。
🔹 多项式阶 O(nᵏ)（k≥3）
迭代为k层嵌套循环，总操作次数为n的k次方级别。
典型场景：三层嵌套的矩阵乘法迭代、高维数据流分析的朴素迭代实现。
特点：输入规模稍大就会出现性能爆炸，工程中通常会用优化算法降低复杂度。
🔹 指数阶 O(2ⁿ)
迭代轮数随输入规模n指数增长，需要枚举全部2ⁿ种状态。
典型场景：枚举所有子集的暴力迭代、无剪枝的全路径数据流MOP分析、暴力枚举所有执行路径的迭代。
特点：仅能处理n≤20的极小输入，n稍大就会完全无法终止，属于不可工程落地的低效复杂度。
所有迭代算法的复杂度增长关系为：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(nᵏ) < O(2ⁿ)，实际工程中会优先选择前四类低复杂度的迭代实现，避免后两类高复杂度的暴力迭代。
需要我帮你整理一份不同复杂度迭代算法的优化技巧清单吗？帮你快速把高复杂度迭代降到更低量级。
0 评论