2024-04-24 02:44:25 发布
网友
def foo(n): def bar(n): if n == 0: return 0 else: return 1 + bar (n - 1) return n * bar(n)
我如何计算foo运行时间的时间复杂度是多少?空间复杂性呢?在
让我们把它分解:
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)。在
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)空间。在
注意:使用尾部递归实现可以进一步降低空间复杂性。在
希望有帮助!在
让我们把它分解:
这在时间和内存上呈线性-
O(n)
。在正如cᴏʟᴅsᴘᴇᴅ所述,对于运行时和空间,它都是O(n)。在
让我试着用递归关系和推导来解释它。在
运行时
对于空间复杂性
将为所有递归调用创建“n”堆栈。 因此,O(n)空间。在
注意:使用尾部递归实现可以进一步降低空间复杂性。在
希望有帮助!在
相关问题 更多 >
编程相关推荐