1

我必须从这个算法中找到递归方程：

    ALGO(n)
    if n <= 2 then return(0)
    else
        y = ALGO(n/3)
        i = 2^n
        while i >= 2 do
            j = (1/2) * log(i) //base 2
            while j > 0 do
                i = i/2
                j = j - 1
        z = ALGO(n/2)
        return(z+y)

我对此进行了推理并得出结论，如果 n<=2，则 T(n) = O(1)

我认为内部 while 是 O(n) （每次迭代时 j 减 1），而外部 while 是 O(logn) （每次迭代时 i 减半），给出 O(n*log( n)):

T(n) = T(n/3) + T(n/2) + O(n*log(n)) 如果 n > 2

这是一个很好的论点吗？

4

1 回答 1

3

两个while循环应该是O(n)：

1. i = 2^n;
2. j = (1/2) * log (i) = 1/2 * n = n/2
3. the inner while executes for n/2 times then j becomes 0, now i = i / 2^(n/2) = 2^(n/2);

现在这个程序将返回到第 1 步，只有 i 减半。所以这两个循环应该是：

n/2+n/4+n/8+... = O(n)

事实上，这也可以从更简单的角度来看。由于循环在 i == 1 之前不会终止，并且对于每次执行 i = i / 2，内部循环将运行 n 次。想象一下，我们将内循环和外循环展平，会有 n 次 i = i / 2，因此这两个循环是 O(n)。

总之，T(n) = T(n/3) + T(n/2) + O(n)。

希望这会有所帮助！

于 2011-07-07T15:12:03.690 回答