0

これらの関数のそれぞれについて、大きな実行時間を見つけます。

  1. T(n) = T(n - 2) + n²
    私たちの答え: n²,n³
  2. T(n) = 3T(n/2) + n
    私たちの答え: O(n log n),O(nlog₂3)
  3. T(n) = 2T(n/3) + n
    私たちの答え: O(n log base 3 of n),O(n)
  4. T(n) = 2T(n/2) + n^3
    私たちの答え: O(n³ log₂n),O(n³)

そのため、各質問の正しい答えを決定するのに苦労しています。

全員が異なる結果を得たので、実行時間について外部の意見を求めています。

前もって感謝します。

4

1 に答える 1

1

少し明確化：
質問の関数は、名前とパラメーターから示唆されるように、実行時関数のようです。より微妙なヒントは、それらがすべて再帰的であり、再帰関数は、アルゴリズムの実行時間を記述する関数を生成するときによくあることです (アルゴリズム自体が正式に再帰を使用していない場合でも)。実際、再帰式はかなり不便な形式であり、アルゴリズムの動作をより適切に要約するためにBig O 表記を使用するのはそのためです。T()n

実行時間関数は、パラメーターに特定の値が与えられた場合に、アルゴリズムの実行時間の [場合によっては概算] 相対値を計算できる、パラメーター化された数式です。この場合のように、実行時関数には通常、 という名前の 1 つのパラメーターがあり、項目nの総数に対応します。アルゴリズムは動作することが期待されます (たとえば、検索アルゴリズムではデータベース内のレコードの総数、ソート アルゴリズムではソートされていないリストのエントリ数、パス検索アルゴリズムでは、グラフ内のノードの数....)。場合によっては、実行時間関数が複数の引数を持つことがあります。たとえば、グラフで何らかの変換を実行するアルゴリズムのパフォーマンスは、ノードの総数と頂点の総数、または 2 つの間の接続の平均数の両方にバインドされる場合があります。ノードなど

したがって、当面のタスク(宿題のように見えるため、私の部分的な答え) は、対応する基本的なアルゴリズムが何であれ、各実行時間関数の上限を修飾するBig O式を見つけることです。タスクは、関数の結果を生成するためのアルゴリズムを見つけて修飾することではありません(この 2 番目の可能性は、CS cursus のアルゴリズム クラスで非常に一般的なタイプの演習でもありますが、明らかにここで必要なものではありません。) 問題は次のとおりです。したがって、コンピューターサイエンス自体よりも数学のほうが多いです。 基本的に、n が無限大に近づくにつれて、これらの関数のそれぞれの限界 (またはその近似) を見つける必要があります。 これ



イリノイ大学アーバナ シャンペーン校のJeff Erikson 教授からのメモは、再発を解決するための優れた入門書です。
再帰問題を解決する近道はいくつかありますが、特に微積分が得意な人であれば、一般的なアプローチは答えを推測し、それを帰納法で証明することです。Excel のようなツール、Python や MATLAB やSageなどのプログラミング言語のいくつかのスニペットは、n^2、n^3、n などの値とともに最初の数百の値 (またはそれ以上) のテーブルを作成するのに役立ちます。関数の項の比率と同様に。これらの表は、多くの場合、関数の閉じた形式を見つけるのに十分な洞察を提供します。

質問にリストされている答えに関するいくつかのヒント:
関数 a)
    O(n^2)は確かに間違っています:
        シーケンスの最初のいくつかの値を簡単に調べると、n^2 が T(n) よりもますます小さくなっていることがわかり
    O(n^3)ます。T(n)n が大きな数に向かって大きくなるにつれて、体系的に大きくなります。よく見ると、これO(n^3)が事実上、この関数の Big O 表記の順序O(n^3 / 6)であることがわかりますが、これは T(n) の値を体系的に超えるより正確な表記です [n のより大きな値の場合、および/または n が無限大に近づくにつれて] しかし、より粗いn^3推定値と比較してわずかな割合でしかありません。帰納法によって、それで
あることが確認できます 。O(n^3 / 6)

T(n) = T(n-2) + n^2  // (1) by definition
T(n) = n^3 / 6       // (2) our "guess"
T(n) = ((n - 2)^3 / 6) + n^2   // by substitution of T(n-2) by the (2) expression
     = (n^3 - 2n^2 -4n^2 -8n + 4n - 8) / 6  + 6n^2 / 6
     = (n^3 - 4n -8) / 6
     = n^3/6 - 2n/3 - 4/3
     ~=  n^3/6      // as n grows towards infinity, the 2n/3 and 4/3 factors
                    // become relatively insignificant, leaving us with the
                    // (n^3 / 6) limit expression, QED
于 2012-10-15T08:16:21.770 に答える