查找公式来描述方法中的递归

Question

我正在努力编写描述 foo 方法的递归性质的公式。

问题是，据我所知，因为每次 n 都除以 2，

二叉树公式应该适用于此。

这表示在每次调用中我们划分数据时，我们得到如下公式：

然后如果我们分析 2 那么 :

我们得到：

也就是说C(N) = log(N + 1), namely O(logN)

这一切都说得通，而且似乎是 foo 方法的正确选择，但这不可能，因为

n = 8 我会得到 3 + 1 次迭代，而不是 n + 1 = 8 + 1 = 9 次迭代

Answer 1

这是您的代码：

void foo(int n) {
    if (n == 1) System.out.println("Last line I print");
    if (n > 1) {
        System.out.println("I am printing one more line");
        foo(n/2);
    }
}

我们可以为它的运行时间 T 写下递归关系，作为传递给它的参数值的函数，n:

T(1) = a, a constant
T(n) = b + T(n/2), b constant, n > 1

我们可以针对不同的 n 值写出一些 T(n) 的值，以查看是否出现一种模式：

n    T(n)
---------
1    a
2    a + b
4    a + 2b
8    a + 3b
...
2^k  a + kb

所以对于 n = 2^k，T(n) = a + kb。我们可以根据 n 求解 k，如下所示：

n = 2^k <=> k = log(n)

然后我们恢复表达式 T(n) = a + blog(n)。我们可以很容易地验证这个表达式是否有效：

a + blog(1) = a, as required

a + blog(n) = b + (a + blog(n/2))
            = b + (a + b(log(n) - 1)
            = b + a + blog(n) - b
            = a + blog(n), as required

你也可以用数学归纳法来做同样的事情。

查找公式来描述方法中的递归

Find formula to describe recursion in method

algorithm

recursion

complexity-theory

equation