1

再帰関係の式は 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を見つけることができますか....どこから始めればよいかわかりません。この関数の再帰関係をどのように記述すればよいですか? ありがとうございました。

4

2 に答える 2

5

最初の再帰関係は通常、分割統治アルゴリズムの実行時間を記述するために使用されます。aここでは、データを分割する1/b部分の数、各部分で使用される元のデータの部分、およびf(n)各「レベル」で必要な時間を示します。たとえば、QuickSort アルゴリズムでは、データ (配列またはリスト) を 2 つの部分に分割し、それぞれが元のデータのちょうど半分 (1/2) であり、分割の各「レベル」で、すべてのn要素 1を通過する必要があります。時間。なので再帰関係は

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

(これは O(n * lg(n)) に評価されます) また、バイナリ検索では、データを 2 つの部分に分割しますが、そのうちの 1 つだけを取得し、各「レベル」の時間は一定であるため、関係は次のようになります。

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

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

このように、帰納法は本質的に再帰アルゴリズムであることがわかります。ここでは 2 回検討します。最初は、開始点 (または終了点 - リストを表示している順序によって異なります) で値を計算する時間です。関数では、この値を返すだけなので、定数 ( C1) です。秒は一歩を踏み出す時です。あなたの関数では、定数でもあります（C2）。直感的に、このアルゴリズムの実行時間は次のようになることがわかります。

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

したがって、場合を除きn = 1、要素に対してアルゴリズムを実行する時間をn要素に対して実行する時間を定義しn - 1ます。BigO 表記では、定数は次のように定義され1、1 要素のケースは考慮されないため、最終的な再帰関係は次のようになります。

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

T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + n(これは、またはに評価されO(n)ます)

さらに読む：

于 2012-03-05T01:06:19.687 に答える
2

長い間再帰関係を書いていませんでしたが、これが答えになるはずです: T(n) = T(n-1) + CONSTANT. あなたの式は次のとおりです。T(n)=aT(n/b)+f(n)。b : 問題を b 個の部分に分割します。f(n) : 問題を解決するためにどれだけの時間が費やされたか a: 問題のインスタンスの数 あなたの問題では、問題を 1 だけ直線的に減らすので、n-1 になります。定数は、問題を解決するのに一定の時間がかかることを意味します

PS: 回帰関係は8年から使っていませんが、こんな感じです。

于 2012-03-04T23:32:38.197 に答える