再帰的探索Big O時間の複雑さ

Question

私は時間の複雑さを知り、関係を理解し​​ようとしています。私の講義ノートはとして再帰的な検索機能について説明します。

find(array A, item I) 
    if(arrayEmpty(A)) return BAD; 
    if(item == A[0]) return GOOD; 
    return find(allButFirst(A), I); 

便利なリンク：

T(n) = 1 + T(n-1) // I understand this 
T(1) = 1 // only one computation, understandable 

が、我々はアンロール：https://www.youtube.com/watch?v=_cG5KZSn1LE

私のノートには、時間の複雑さのための開始の関係は以下の通りであることを述べていますT（n）

T(N) = 1 + 1 + T(n-2) // every recursive step 1 comparison plus recursive call 
T(N) = 1 + 1 + 1 + T(n-3) 
T(N) = 1 + 1 + 1 + 1 + T(n-4) 
... 
T(N) = (n - 1) + T(n-(n-1)) // This point I am lost how they got this generalisation 

誰かが上記の関係はT（N）=（n-1）+ T（n-（n-1））に一般化され、おそらく一例は明快にするために良い。

は、例えば、私はそうのは言わせて、いくつかの値を使用して上記の関係を試してみたい、{1、2、3}とI = 3

は、ここに

1 + T(n-1) // {2,3} 
1 + 1 + T(n-2) // {3} 
1 // {3} Found 

そこらの次の計算されています上記の合計3回の比較と2回の再帰呼び出しがありました。だから私は関係がT（n）= n + t（n-（n-1））= n + t（1）= nであると言うでしょう。アンロールパターンの各ステップにおいて

Answer 1

我々は再帰へkステップである場合、（第一工程、k=1、最後のステップ、k=nため）、k 1つのがあります。 T(n-(n-1))はその行、k=n-1ためので、T(1)に展開するのであなたが投稿拡張、最後の行、T(N) = (n - 1) + T(n-(n-1))で

は、最後から2番目のステップです。

したがって、その行にはn-1があります。したがって、(n-1)という用語があります。

同様に、k番目のステップでTに渡されるパラメータは、nから現在のステップを差し引いたもので、残りのステップ数です。最初の行はn-k = n-1であり、したがってT(n-1)です。 2番目から最後のステップでは、n-k = n-(n-1)、したがってT(n-(n-1)) = T(1)です。