2 
def foo(x):
    if x > 5:
        return foo(x–1) – foo(x-1)
    else:
        return 11

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

我如何找到运行时间Big O notation以及惰性评估（在需要表达式的值之前不评估表达式）如何影响这一点？

第一个是O(n)由于单个递归调用，第二个是O(n^2)由于另一个递归调用中的递归调用吗？我只知道如何根据我之前看到的例子进行猜测。:(

4

1 回答 1

3
  • foo()是O(2^n)（假设interpeter没有缓存优化）。
  • bar()是O(infinity)（从不终止），并且O(n)使用惰性求值

说明：
每个foo(n)调用 2 次调用，f(n-1)因此您将获得复杂度函数：

T(n) = T(n-1) + T(n-1) = T(n-2) + T(n-2) + T(n-2) + T(n-2) = ... = 2^(n-5)*T(5)

（这...部分可以用数学归纳法形式化证明）

处于无限循环中，bar(n)因为假设b>0- 它将被递归调用b+1- 这也将满足约束b>0。通过归纳，您可以得到对于所有b>0的额外调用bar()with b'>b- 这会导致无数次调用bar()- 因此O(infinity)

使用惰性求值，第二种方法 ( bar()) 变为O(n).
这是因为无限递归仅发生在评估a- 但是，因为a从未真正使用过 - 不需要评估参数的表达式a，并且因为b减少了每个递归调用 - 你得到O(n)

的正式证明T(n) = T(n-1) + T(n-1)在O(2^n)：

基数： T(5) = CONST
假设：T(k) <= CONST * 2^k对于每个k<n
证明：

T(n) = T(n-1) + T(n-1) <= (assumption) <= CONST* 2^(n-1) + CONST* 2^(n-1) = 
     = CONST*2*2^(n-1)  = CONST * 2^n

从数学归纳法我们可以得出结论，假设是正确的，并且T(n)在O(2^n)

于 2012-11-29T09:10:26.903 回答