仅在循环末尾执行一次线性复杂度函数时的总时间复杂度是多少？

函数f(n)的最终时间复杂度为O(n)，不是O(n²)。

推导过程 #

• 外层for循环总共执行n次：前n-1次循环仅执行i==n-1的条件判断，单次判断是O(1)复杂度，前n-1次总耗时为O(n)
• 仅最后一次循环（即i = n-1时）会调用some_linear_complexity_function()，该函数自身是O(n)线性复杂度，这一步耗时为O(n)
• 总时间开销为两部分相加：O(n) + O(n) = O(n)，大O表示法会忽略常数系数，多个同阶线性项叠加后仍然是线性复杂度。

常见误区说明 #

很多人容易误判为O(n²)，是混淆了「O(n)函数执行n次」和「O(n)函数仅执行1次」的情况：只有当外层每一轮循环都执行O(n)操作时，总复杂度才是O(n²)，本题中线性复杂度的函数仅触发1次，不会出现平方级的开销。

举个直观的例子：当n=100时，总操作量是前99次判断 + 最后1次100步的线性函数，总步数为199，和n成线性比例，远达不到100*100=10000的平方级规模。

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