0 
def foo(x):
    if x > 5:
        return foo(x–1) – foo(x-1)
    else:
        return 77

def bar(a,b):
    if (b > 0):
        return bar( bar(a, b+1) , b-1 )
    else:
        return 0

有人walk me through可以找到这些的运行时间吗？对于foo，我的猜测是这是O(n^2)由于 2 次递归调用。也可以Θ(n^2)吗？

因为bar，我不知道，因为它是无限递归。

4

2 回答 2

0

显然foo(n)不在多项式时间内：

T(n) = 2T(n-1)  , if n > 5
     = Theta(1) , otherwise

因此

T(n) = Theta(2^n)

bar(a,b)只要永远不会结束b > 0

于 2012-11-29T08:53:09.750 回答
0

对于函数

          _________  77  if(x<=5)
         /
        /
 foo(x)- 
        \
         \_________    foo(x-1) - foo(x-1)   if(x>5)


let f(x) be time function for foo(x)

f(x) =   f(x-1) - f(x-1) // 2 (2^1)calls of f(x-2) happened for 1 level depth
f(x) =   [f(x-2) - f(x-2)] - [ f(x-2) - f(x-2)] (expanding f(x-1)) // 4(2^2) calls of f(x-2) happened for 2nd level depth
f(x)={[ f(x-3) - f(x-3)]-[ f(x-3) - f(x-3)]} - {[ f(x-3) - f(x-3)]-[ f(x-3) - f(x-3)]} // 8(2^3) calls  of  f(x-2) happened for 3rd level depth

让我打电话已经完成程序....

but program terminates when x<=5,
 so program terminates in call f(x-i) when x-i<=5
that means i>=x-5 , 
at level i there are 2power(i) calls 
 ==> 2^i calls of f(x-i).
 since f(<=5)=1(1 is unit of measure) for i>=x-5

所以 f(n) = 2^(x-5)*(1) =>O(2^x) 其中 x 是输入大小。如果我们用 n 替换 x 复杂度是 O(2^n) 。

第二个问题

          _________  0  if(b<=0)
         /
        /
 bar(a,b)
        \
         \_________  foo( bar(a,b+1) ,b-1 )  if(b>0)

令 t(n) 为 bar(a,b) 的时间函数，其中 n 与 b 成正比，因为 b 是终止的决定因素。

扩大递归

t(a,b) = t( t(a,b+1), b-1) .
first  t(a,b+1) is executed it inturn calls t(a,b+2) and so on.... 
it will be infinite recursion .....   for b > 0  .

据我所知，由于我们没有无穷大的限制（既没有下限也没有上限，所以没有 theta 表示法和大哦表示法，比如 omega 表示法）我们也无法测量复杂度函数。（如果我有请纠正我'我错了）

但是如果 b<0 那么它将在 O(1) 时间内完成......

于 2012-11-29T09:17:02.973 回答