时间复杂度为O(f(m)*n)且0<f(m)<1时能否简化为O(n)？

你可以省略f(m)项，直接判定该函数的时间复杂度为O(n)。

大O符号的核心作用是描述算法运行时间增长的上界，我们可以直接用它的定义来推导：

• 大O的判定规则为：如果存在正的常数C和自变量临界值N₀，当n ≥ N₀时，函数运行时间T(n)始终满足T(n) ≤ C * g(n)，就可以判定T(n) = O(g(n))
• 题目已经明确f(m)是输出值严格处于(0,1)区间的非随机函数，也就是说对任意合法的m取值，都满足f(m) ≤ 1
• 代入原式可得：f(m) * n ≤ 1 * n = n，完全符合大O上界的判定要求，因此f(m)可以直接被吸收进大O的常数项中省略

这个结论仅适用于大O上界的判定场景，有两个特殊情况需要额外注意：

• 如果f(m)的取值范围没有固定的常上界，而是会随m或其他自变量增长，就不能直接省略
• 如果你需要计算更精确的时间复杂度下界（Ω表示法）、紧界（Θ表示法），或是要估算实际运行耗时，还是需要保留f(m)项做具体计算

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