確定遞歸函數的時間和空間複雜度

def foo(n): 
    def bar(n): 
     if n == 0: 
      return 0 
     else: 
      return 1 + bar (n - 1) 
    return n * bar(n)

如何根據輸入n計算foo運行時間的時間複雜度？空間複雜性呢？確定遞歸函數的時間和空間複雜度

來源

2017-09-01 kiki

請修復您的縮進。 –

@ChristianDean試圖？ :) OP：它有多少次遞歸堆棧 - 這應該給你一個空間和時間複雜性的線索。 – AChampion

@AChampion嗯，爲什麼沒有爲我工作：| –

讓我們來分析一下：

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)。

來源

2017-09-01 01:41:37

爲什麼它不像bar（），步數是n + 1，而foo（）是n（n + 1），所以時間：O（n^2）？ – kiki

@kiki錯了。乘法是一個不變的操作。 n * n是一個單獨的步驟。然而，計算柱的輸出是線性的。 –

正如cmentionedsᴘᴇᴇᴅ提到的，對於運行時和空間都是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）空間。

說明：空間複雜度可以通過尾遞歸實現進一步降低。

希望它有幫助！

來源

2017-09-20 13:25:29 arunk2

確定遞歸函數的時間和空間複雜度

回答

相關問題