def foo(n):
def bar(n):
if n == 0:
return 0
else:
return 1 + bar (n - 1)
return n * bar(n)
如何计算FOO在其输入N方面的运行时间的时间复杂性是多少?空间复杂性呢?
让我们分解:
return n * bar(n)
→ n * (1 + bar(n - 1))
→ n * (1 + 1 + bar(n - 2))
→ n * (1 + 1 + 1 + bar(n - 3))
→ n * (1 + 1 + 1 + .... <n times> + bar(0))
→ n * n
这在时间和内存中出现线性-O(n)
。
,如CᴏʟᴅSᴘᴇᴇᴅ所述,对于运行时和空间,它是 o(n)。
让我尝试用复发关系和推导来解释它。
用于运行时
Base case: T(0) = 1
Recurion : T(n) = T(n-1) + 1 (constant time for addition operation)
T(n) = T(n-1) + 1
= T(n-2) + 1 + 1
= T(n-3) + 1 + 1 + 1
= T(n-4) + 1 + 1 + 1 + 1
= T(n-4) + 4*1
...
= T(n-n) + n * 1
= T(0) + n * 1
= 1 + n
= O(n)
用于空间复杂性
将为所有递归调用创建'n'堆栈。因此,o(n)空间。
注意:可以通过尾部递归实现进一步降低空间复杂性。
希望它有帮助!