找出递归算法的运行时间（主定理）

Question

这是我要计算运行时间的算法：

T(n) = {
        c0 * n, if n <= 20
        T(roundUp(n/4)) + T(roundUp(5/12 * n + 3/2)) + c1*n, if n > 20
       }

n为正自然数的一部分，c0、c1为常数

这里是java中的算法-代码：

    public static void main(String[] args) {
        for (int i = 20; i < 100; i++) {
            System.out.println("i: " + i + " :    " + rec(i, 1, 1));
        }
    }

    public static int rec(int n, int c0, int c1) {
        int res = 0;
        if (n <= 20) {
            res += c0 * n;
        } else {
            double temp = n / 4d;
            double temp2 = n * (5 / 12d) + (3 / 2d);
            res += rec((int) Math.ceil(temp), c0, c1) + rec((int) Math.ceil(temp2), c0, c1) + c1 * n;
        }
        return res;
    }

我正在寻找一种方法或一个解释示例。

Answer 1

嗯，好久没做了，还没人回答，我试试看。你基本上在这里创建树，有两个重要的 children。左一基于temp = n / 4d，右一基于temp2 = n * (5 / 12d) + (3 / 2d)。那么问题来了，这棵树有多深？因为 n / 4d 会比 n * (5 / 12d) + (3 / 2d) 更快地结束在 20 之下，所以我们只关心正确的 child。那么问题来了，根据n到底有多少children呢？当我们迭代时，我们有这个：

n * (5 / 12d) + (3 / 2d) 
ceil(n * (5 / 12d) + (3 / 2d) ) * (5 / 12d) + (3 / 2d)
ceil(ceil(n * (5 / 12d) + (3 / 2d)) * (5 / 12d) + (3 / 2d) ) * (5 / 12d) + (3 / 2d)
...

这里，我们也可以忽略3/2d部分，以及与之相关的一切，所以我们得到：

n * (5 / 12) ^ k < 20

其中 k 是到达最右边的步数 child，所以我们有：

n * (5 / 12) ^ k < 20
k = log_(5 / 12) (20 / n)
k = log_2(20 / n) / log_2 (5 / 12)   
k = (log_2 (20) - log_2(n) ) / log_2 (5 / 12)

自此:

k = log_2 (20) / log_2 (5 / 12)

是一个具体的数字，我们可以忽略它...

k = - log_2(n) / log_2 (5 / 12)

开始于：

log_2 (5 / 12)  < 0

我们还剩下：

k = log_2(n) = lgn

正如预期的那样，因为我们只处理树，所以你得到 O(n) = lg(n)。

找出递归算法的运行时间（主定理）

Find Out The Running Time Of A Recursive Algorithm (Master-Therorem)

java

algorithm

performance

recursion

master-theorem

找出递归算法的 运行 时间（主定理）

Find Out The Running Time Of A Recursive Algorithm (Master-Therorem)

java

algorithm

performance

recursion

master-theorem

找出递归算法的运行时间（主定理）