再帰関数の時間と空間の複雑さを決定する

Question

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

fooの実行時間の複雑さは、入力nの観点からどのように計算できますか？空間の複雑さはどうですか？

Answer 1

のは、それを打破してみましょう：

は

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

Answer 2

cᴏʟᴅsmentionedで述べたように、ランタイムとスペースの両方で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）スペース。

注：テール再帰実装では、空間の複雑さをさらに減らすことができます。

希望すると助かります！