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 表示法 中的运行时间以及延迟求值(在需要表达式的值之前不求值表达式)有何影响？
第一个是 O(n) 由于单个递归调用，第二个是 O(n^2) 由于另一个递归调用中的递归调用？我只知道如何根据我以前见过的例子进行猜测。 :(
最佳答案
-
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)
(...部分可以使用mathematical induction来形式化证明)
bar(n)处于无限循环中，因为假设 b>0 - 它将被递归调用b+1 - 这也将满足约束 b>0 。通过归纳，你可以得到所有b>0有一个额外的调用 bar()与 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)
关于python - 大 o 表示法和惰性求值的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13620069/