19

単純な再帰メソッドの大きな O を判断するのに苦労しています。メソッドが複数回呼び出されたときに何が起こるかについて頭を悩ませることはできません。私は混乱している分野についてより具体的に述べたいと思いますが、現時点ではいくつかのハードウェアに関する質問に答えようとしています。カンニングをしたくない代わりに、この投稿に返信する人に簡単な再帰的な方法を考え出すようお願いします。上記の方法の大きなOの簡単な説明を提供します. （できればJavaで...私が学んでいる言語です。）

ありがとうございました。

4

2 に答える 2

34

順序を再帰的に定義することもできます。たとえば、関数 f があるとします。f(n) を計算するには、k ステップかかります。ここで、f(n+1) を計算します。f(n+1) が f(n) を 1 回呼び出し、次に f(n+1) が k + 定数ステップを取るとします。各呼び出しには一定のステップが余分にかかるため、このメソッドは O(n) です。

次に、別の例を見てください。前の 2 つの結果を追加して、単純にフィボナッチを実装するとします。

fib(n) = { return fib(n-1) + fib(n-2) }

ここで、 fib(n-2) と fib(n-1) の両方を約 k ステップで計算できるとしましょう。fib(n) を計算するには、k+k = 2*k ステップが必要です。ここで、fib(n+1) を計算するとします。したがって、fib(n-1) の場合の 2 倍のステップが必要です。これは O(2^N) のようです

確かに、これはあまり形式的ではありませんが、うまくいけば、この方法で少し雰囲気をつかむことができます。

于 2012-07-31T23:10:10.717 に答える
18

再帰メソッドのビッグ O を見つけるために、マスター定理を参照することをお勧めします。ウィキペディアの記事は次のとおりです。 http://en.wikipedia.org/wiki/Master_theorem

ツリーのような再帰的な問題を考えたいとします。次に、ツリーの各レベルと必要な作業量を検討します。問題は通常、ルートが重い (最初の反復 >> ツリーの残りの部分)、バランスの取れた (各レベルの作業量が等しい)、リーフが重い (最後の反復 >> ツリーの残りの部分) の 3 つのカテゴリに分類されます。

マージソートを例にとると:

define mergeSort(list toSort):
    if(length of toSort <= 1):
        return toSort
    list left = toSort from [0, length of toSort/2)
    list right = toSort from [length of toSort/2, length of toSort)
    merge(mergeSort(left), mergeSort(right))

mergeSort を呼び出すたびに、元の長さの 1/2 のさらに 2 つの mergeSort が呼び出されることがわかります。マージ手順には、マージされる値の数に比例して時間がかかることがわかっています。

再帰関係は、T(n) = 2*T(n/2)+O(n) です。2 つは 2 つの呼び出しからのもので、n/2 は要素の数が半分しかない各呼び出しからのものです。ただし、各レベルには、マージする必要がある同じ数の要素 n があるため、各レベルでの一定の作業は O(n) です。

作業が均等に分散され (深さごとに O(n))、ツリーの深さが log_2(n) であることがわかっているため、再帰関数の大きな O は O(n*log(n)) です。

于 2012-07-31T23:15:08.537 に答える