time-complexity - 两个不同递归函数相互调用的时间复杂度

Question

分析相互调用的两个不同递归函数的时间复杂度的最佳方法是什么。

class test {
public:
    static int f(int x) {
        if(x < 1) return 1;
        return f(x - 1) + g(x);
    }
    
    static int g(int x) {
        if(x < 2) return 1;
        return f(x - 1) + g(x / 2);
    }
    
};

test.f(n) 这里的时间复杂度是多少？

我试图画一棵递归树。我的衰退树的高度是 n。对于每个级别，有两个函数调用，即 f 和 g。我试图用 f(x - 1) + g(x / 2) 代替 g(x)。因此，对于 f(x) 的每个函数调用，都会创建两个新的 f(x - 1) 分支和一个 g(x / 2)。我刚刚迷路了，接下来我该怎么办？

标签： time-complexityruntimebig-o

Answer 1

这真的很混乱，但我相信这是正确的——如果不是，我会很乐意解决这个问题。
（我真的希望 StackOverflow 只将 LaTeX 应用于这类问题。）

---

我们首先需要制定这两个递归函数，因此根据您代码中的定义，我们可以将这两个函数编写为：

然后我们可以替换g(n)为第一个递归函数f：

---

但什么是g(n/2)？好吧，根据定义，它是：

再次，什么是g(n/4)？...我们得到了这个想法，它一直持续到我们命中g(1)- 这发生在大约~lg(n)“循环”之后，因为我们想要解决这个等式：

---

所以最后，我们得到了最后的递归调用f：

请注意，我没有添加-1内部f，因为它不会真正影响这里的渐近符号。

然后我们可以使用以下方法解决它：

第一个可以使用迭代方法完成，而后者可以使用Akra-Bazzi 方法解决。

---

为简单起见，我用 Python 编写了代码

def f(x):
    if x < 1:
        return 1
    return f(x-1) + g(x)
    
def g(x):
    if x < 2:
        return 1
    return f(x-1) + g(x/2)

iterations = 40
for i in range(1, iterations + 1):
    print(f'i={i}')
    solvefn = f(i)
    print(f'Actual: {solvefn}')
    guess_c = solvefn / 2 ** i
    print(f'c={guess_c}')
    print('------------')

f(n)并且想通过比较for some ns to的解来看看它是如何进行的2 ** n，这就是我得到的（注意我的计算能力不是那么高，这两个递归关系非常昂贵，因为如果解是正确的，它是指数运行时间）

i=28
Actual: 527053651
c=1.9634278528392315
------------

i=29
Actual: 1054123325
c=1.9634576980024576
------------

i=30
Actual: 2108278696
c=1.9634875431656837
------------

---

这意味着我们的猜测2**n实际上小了大约一半，但是，回想一下big-o 符号的定义，我们可以选择任何有限常数c，因此我们可以选择c=2“修复”这个问题。

---

附录

因为 Akra-Bazzi 需要一个特定的p值来解决这个总和：

起初我以为p=0会解决它，这是胡说八道（发生这种情况是因为我先评估了总和，然后尝试解决它p）-无论如何，我认为它不应该克服O(2 ** n)，但我没有正式的证明为此，也许应该考虑更多的计算。

---

附录 V.2

我想我可能已经找到了解决它的方法，我们需要找到一个p可以解决上面附录中的和的方法，当然，这是一个众所周知的几何级数，1只有当p=1（并且n接近无穷大，如我们想要，因为我们在谈论渐近符号），这里有一个很好的视觉证明

使用这个，我们可以使用 Akra-Bazzi 方法来解决它：