如何根据给定约束条件确定算法的时间复杂度？

核心逻辑：先算「运算次数上限」，再匹配复杂度 #

题目里给的n=1「n<=nums.length」「n<=1e5」这类约束，本质是告诉你程序能承受的最大运算次数阈值。行业默认1秒内能跑约1e8次基础运算（比如加减乘除、数组访问），把n的约束代入不同复杂度公式，算出运算次数，看是否在阈值内就行。

常见约束对应的复杂度匹配 #

直接上实例，一眼就能懂：

• 极小约束（n≤20）：能扛住O(2ⁿ)（暴力递归、回溯）。比如2^20≈1e6，远小于1e8，全排列、子集这类问题随便造。
• 小约束（n≤100）：能扛住O(n³)（三重循环）。100³=1e6，Floyd最短路径、三维DP都没问题。
• 中等约束（n≤1e3）：能扛住O(n²)（双重循环）。(1e3)²=1e6，冒泡排序、二维DP、邻接矩阵图算法都稳；要是n到1e4，(1e4)²=1e8，刚好卡阈值，得优化下常数项。
• 大约束（n≤1e5）：能扛住O(n log n)（排序、分治）。1e5*log₂(1e5)≈1.7e6，远低于阈值，快速排序、归并排序、二分变种都能用。
• 超大约束（n≤1e6及以上）：只能用O(n)（线性遍历）或O(log n)（纯二分）。1e6次运算完全没问题，前缀和、双指针、哈希表遍历都是首选。

精确复杂度vs近似复杂度的判断 #

精确复杂度 #

就是写出算法的具体循环/操作次数：

• 单循环从0到n-1：O(n)
• 外层n次、内层n次的嵌套循环：O(n²)
• 每次把问题规模减半（比如二分）：O(log n)
  比如冒泡排序最好情况是O(n)，最坏是O(n²)，这就是精确复杂度。

近似复杂度（渐进复杂度） #

忽略常数项和低阶项，只保留最高阶的项：

• 比如算法实际运算次数是3n² + 5n + 10，近似复杂度就是O(n²)——当n很大时，低阶项和常数项的影响可以忽略，比如n=1e5时，3n²是3e10，5n才5e5，根本不在一个量级。

特殊约束细节处理 #

• 如果是n=1：随便写，哪怕直接返回结果的O(1)都没问题；
• 如果是n<=nums.length：先看题目给的nums.length范围（通常会标注，比如1e5），再按上面的规则匹配复杂度。

内容的提问来源于stack exchange，提问作者INDIAN_ GAURAV_