You need to enable JavaScript to run this app. 如何证明给定函数f(n)的时间复杂度为O(n^4)
优惠活动
大模型
产品
解决方案
定价
更多

如何证明给定函数f(n)的时间复杂度为O(n^4)

多独立常数场景下的大O复杂度严谨证明

现有推导进度

你已经完成的推导步骤:

  • 待证明目标:函数 f(n) = c_0 + n * c_1 * n * c_2 * (n(n+1))/2 * c_3 属于 O(n^4) 复杂度
  • 已整理的不等式方向:对任意n满足 f(n) <= c * n^4,进一步展开得到 c_0 + c_1 * c_2 * c_3 * (n^4 + n^3) <= 2c * n^4

核心规则澄清

大O定义中要求的常数c是与n无关的固定正数值,原式里出现的所有和n无关的独立常数(比如这里的c_0,c_1,c_2,c_3),都可以直接合并进同一个待选的c中,不需要单独拆分处理。


完整推导步骤

  1. 低次项上界收缩:当n >= 1时,恒有n^3 <= n^4,这个不等式和任何常数取值都无关
  2. 代入原式消去低次项:
    f(n) = c_0 + c_1*c_2*c_3*(n^4 +n^3)/2
    <= c_0 + c_1*c_2*c_3*(n^4 +n^4)/2
    = c_0 + c_1*c_2*c_3 *n^4
    
  3. 常数项上界收缩:当n >=1时,固定常数c_0满足c_0 <= c_0 * n^4(因为n^4在n>=1时取值恒大于等于1)
  4. 再次代入合并项:
    f(n) <= c_0 *n^4 + c_1*c_2*c_3 *n^4
    = (c_0 + c_1*c_2*c_3) *n^4
    
  5. 选定符合大O定义的参数:
    • 固定常数c = c_0 + c_1*c_2*c_3
    • 阈值n_0 =1
      完全满足大O的核心判定要求:对所有n >=n_0,恒有f(n) <=c *n^4

卡壳原因说明

你之前推导到出现多个独立常数时的犹豫,本质上是误以为需要给每个常数单独赋值、拆分不等式求解c,但实际上大O只关注函数的增长阶,不关心常数项的具体数值——哪怕c是由多个独立常数相加/相乘得到的结果,只要它不随n的变化而变化,就完全符合定义要求。

内容的提问来源于stack exchange,提问作者JakeDrone

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.20 23:06:06