-2

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

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;
    }

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

4

1 回答 1

1

嗯，好久没做这个了，还没人回答，我试试。你基本上在这里创建树，有两个重要的孩子。左一个是基于temp = n / 4d，右一个是基于temp2 = n * (5 / 12d) + (3 / 2d)。所以问题是，这棵树有多深？既然会很快n / 4d结束，那么我们只关心正确的孩子。所以问题是，有多少最右边的孩子是基于？当我们迭代时，我们有这个：20n * (5 / 12d) + (3 / 2d)n

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到达最右边的孩子的步数在哪里，所以我们有：

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).

于 2016-05-04T10:45:04.190 回答