関数の再帰関係の書込み

Question

私は漸化式の式がT（n）= aT（n/b）+ f（n）であることを知っています。そして、私はBigOを解く方法を知っています。私の宿題の質問では、リスト内のノードの数を数えるための再帰関数を作成するように求められましたが、その後再帰関係を作成するように求められました。ここに私のコードは次のとおりです。

int count(ListNode *l) 
{ 
    if(!l) return 0; 
    if(!l->next) return 1; 

    return 1 + count(l->getNext()); 
} 

しかし、私は私自身の漸化式を策定/作成方法に完全に失われています...私はaまたはbを見つけるのですか....私はどこから始めするか分かりません。この関数の反復関係はどうやって書くのですか？ありがとうございました。

Answer 1

私は長い時間から再帰関係を書いていませんが、答えは T（n）= T（n-1）+ CONSTANTです。あなたの公式は、T（n）= aT（n/b）+ f（n）です。 b：問題をb部分で分けます。 f（n）：問題の解決にどれくらいの時間を費やしますか a：問題のインスタンス数 問題を1で線形的に減らしてn-1にします。定数は、問題を解決するために一定の時間がかかることを意味します。

PS：私は8年からの再帰関係を使用していませんが、これはその方法です。

Answer 2

通常、最初の反復の関係は、の実行時間を説明するために使用され、アルゴリズムを分割します。 aここでは、データを分割する部分の数を示します。1/bは、各部分で使用されている元のデータを示し、f(n)は、各レベルでどれくらいの時間が必要かを示します。たとえば、QuickSortアルゴリズムでは、データ（配列またはリスト）を元のデータの1/2に相当する2つの部分に分割し、分割するそれぞれの「レベル」ごとにすべてn要素を通過する必要があります1回。だから、再発関係は

（O（N * LG（N）に評価される））

T(n) = 2T(n/2) + n 

で、バイナリ検索であなたは、2つの部分にデータを分割するが、唯一の1にそれらのを取り、それぞれ「レベルの時間"は一定なので、関係は次のようになります。

T(n) = T(n/2) + 1 

ただし、Cの関数は分裂征服戦略に従いません。代わりに数学的誘導を示しています。開始条件を定義します。lがNULLの場合は長さが0、l->nextがNULLの場合（リスト内の1要素の条件も定義します）。次に、一種の帰納的ステップを定義します。（n-1）番目の要素の関数値を知っている場合、n番目の要素の関数を計算する方法を定義します。したがって、第1要素の関数の値を知っていれば、この規則を適用して2番目の要素、3番目の要素などの値を取得できます。

誘導方法は本質的に再帰アルゴリズムであることがわかります。ここでは2回考えます。最初は、開始点（またはエンドポイント - これはリストを見ている順序に依存します）で値を計算する時間です。あなたの関数ではこの値を返すだけなので、定数（C1）です。 2番目は1ステップを作る時間です。あなたの関数では、それも一定です（C2）。直感的に、あなたは、このアルゴリズムの実行時間がされるはずです。

T(n) = C1, when n = 1 
T(n) = T(n - 1) + C2, when n > 1 

したがって、n = 1ない限り、あなたはn - 1要素の上にそれを実行するための時間を通じてn要素にアルゴリズムを実行する時間を定義します。

T(n) = T(n - 1) + 1 

（ T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + nに評価、または O(n)）

またを読み取る

：最終的な漸化式であるので、ビーゴ表記で任意定数が1と1つの要素の場合のように定義されるが、考慮されていません。

• Introduction to Algorithms Thomas H. Cormen。
• Art of Computer Programming Donald Knuth著