根据我的说法，给定递归函数的时间复杂度是 O(1/n)，这可能吗？

Question

我认为下面代码的时间复杂度应该是 O(1)，因为最坏的情况可能是 log 1000 base 2 或某些确定的值。但我不确定，因为它的时间确实随着输入的变化而变化，并且给定的答案是 O(n)，我对他们是如何得到这个感到非常困惑。如果我们增加 n，函数被调用的次数就会减少，那么它是 O(1/n) 吗？有可能吗？

#define LIMIT 1000

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

Answer 1

#define LIMIT 1000以及if (n > LIMIT) return;保证 O(1) 的基本情况，因为它对函数可以运行的迭代次数设置了上限。

即使这是#define LIMIT 10e50，它仍然是 O(1) 。

回想一下，Big O 关心的是理论增长，而不是实践中要做多少工作。如果您对函数可以增长的程度有一个上限，无论该上限有多大，从复杂性的角度来看，这都是一个恒定时间操作。

Big O 一定是算法所做工作的现实反映吗？不。Big O 是一种可扩展性启发式方法，而不是效率的最终定论。这里所说的所有 O(1) 是，一旦n > LIMIT，您可以无限期地增加n，而无需额外成本。在现实世界中，恒定因素往往很重要。