递归函数时间复杂度能否为O(1/n)？C++递归代码复杂度咨询

代码逻辑梳理 #

我们先明确待分析的代码实现：

#define LIMIT 1000

void fun2(int n)
{
  if (n <= 0)
     return;
  if (n > LIMIT)
    return;
  cout<<n<<" ";
  fun2(2*n);
  cout<<n<<" ";
}

函数的执行规则非常明确：

• 当输入n≤0或者n>LIMIT时，函数直接返回，不做任何输出和递归调用
• 当0<n≤LIMIT时，函数会先打印n，再递归调用fun2(2*n)，递归返回后再打印一次n

核心问题解答 #

• 关于「时间复杂度为O(1)」的判断：这个结论是正确的。大O记号的核心定义是，当输入规模趋向无穷大时，算法执行步数的上界是否存在一个和输入规模无关的固定常量。对这段代码来说，只要输入n>1000，函数只需要执行两次判断就直接返回，仅需常数步操作；就算是触发最多递归的输入n=1，总递归深度也只有log₂(1000)≈10层，算上每层的两次打印操作，总执行步骤也就20次左右，这个上限是完全固定的，和输入n的大小没有任何关系。O(1)复杂度从来不要求所有输入的执行时间完全一致，只要求执行时间的上界不随输入规模增长即可。
• 关于「资料给出O(n)结论」的原因：所有给出O(n)结论的分析，针对的都是去掉了if (n > LIMIT) return;这个固定常量终止条件的变体题目。这类变体要么把终止条件改成和输入n相关的判断，要么把递归参数改成线性变化的形式，执行步数会随n的增长而线性上升，和你贴的这段带硬编码常量上限的代码不是同一个实现。
• 关于「是否存在O(1/n)复杂度」：不存在这种时间复杂度。算法的执行步数最少为1（完成参数判断、函数返回的最小操作集），不可能随着输入规模增大无限趋近于0。你观察到的「n增大、调用次数减少」的现象，只存在于0<n≤1000这个有限的输入区间内，当n超过1000之后，不管n取多大值，执行步数都固定为常数，不会继续下降，完全不符合1/n的变化趋势。

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