0

就该函数的算术运算而言（就上限而言），时间成本是多少？

int foo(int n)
{
    int i;
    if (n <= 3) return 1;
    else if (n > 333) 
    {
        i = n/2;
        return 3 * foo(i) + foo(i) + n * i; 
    }
    else return foo(n - 3) + 9; 
}

我试图分析它，这些是我的想法：

  1. T(n) 是：

       1; 如果 n ≤ 3
   4T(n/2) + (n 2 )/2 ; 如果 n > 333       
   T(n-3) + 9 ; 否则

  2. 所以对于第二个等式，我可以说它是。O((n2)/2 logn)

这是对的吗？

4

1 回答 1

3

不要被抛出到函数中的所有操作所迷惑，这些操作只是恒定时间操作。加法、乘法、比较——这些都是常数时间运算。分支递归是您需要关注的。

在完全不改变复杂性的情况下，我可以将函数重新排列为这个等价物：

int foo(int n)
{
    if (n <= 3) return 1;
    else if (n <= 333) return foo(n - 3) + 9;
    else
    {
        int i = n/2;
        return 3 * foo(i) + foo(i) + n * i; 
    }
}

前两种情况基本说“当n小于某个固定常数时，还有一个有界常数的工作要做。” 所以我们最终得到的唯一方法O(1)是最后一个else块。

在那里，唯一的非常量时间操作是对foo(n/2). 所以我们有递归关系

T(n) = T(n/2) + T(n/2) = 2T(n/2)

产生

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

所以 的复杂度foo(n)是O(n)。

WolframAlpha 同意我的看法：
http ://www.wolframalpha.com/input/?i=T%28n%29+%3D+2*T%28n%2F2%29

您必须具有表格的重复关系T(n) = O(n) + 2*T(n/2)才能得到T(n) = O(n log n). WolframAlpha 再次同意：
http ://www.wolframalpha.com/input/?i=T%28n%29+%3D+n+%2B+2*T%28n%2F2%29

于 2013-06-20T16:59:12.033 回答