再帰的メソッドの大きなOX

Question

単純な再帰的メソッドの大きなOを決定するのが難しいです。メソッドが複数回呼び出されたときに何が起こるのか、私の頭を包み込むことはできません。私は自分の混乱の領域についてより具体的になるだろうが、現時点ではいくつかのhw質問に答えることを試みている。そして、不正行為をしたくないのではなく、この投稿に答える誰も簡単な再帰的方法上記の方法の大きなOの簡単な説明を提供する。 （できるだけJavaで...私が学んでいる言語）

ありがとう。

Answer 1

順序を再帰的に定義することもできます。たとえば、関数fがあるとします。 f（n）を計算するにはkステップが必要です。今度はf（n + 1）を計算します。 f（n + 1）がf（n）を1回呼び出すと、f（n + 1）はk +一定のステップを要します。各呼び出しにはいくつかの一定のステップが余計にかかるので、このメソッドはO（n）です。

もう1つの例を見てください。

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

今、あなたは、FIB（N-2）を計算することができると言うことができますし、FIB（N-1）についてのk個のステップで両方：あなたは前の2つの結果を追加することによって、単純にフィボナッチを実装すると言うことができます。 fib（n）を計算するには、k + k = 2 * kステップが必要です。ここでfib（n + 1）を計算したいとします。だから、fib（n-1）の2倍のステップが必要です。これはO（2^N）と思われます。

確かに、これはあまり正式ではありませんが、うまくいけばこのように感じることができます。

Answer 2

再帰的メソッドの大きな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)) 

あなたが順番にマージソートの各呼び出しは1/2元の長さの2以上mergeSortsを呼び出すことがわかります。マージ処理には、マージされる値の数に比例した時間がかかります。

したがって、漸化関係は、T（n）= 2 * T（n/2）+ O（n）です。 2つは2つのコールから得られ、n/2は各コールからのものであり、要素の数の半分しかありません。しかし、各レベルにはマージする必要のある要素数nが同じであるため、各レベルでの定数作業はO（n）です。

木がlog_2（n）の深さなので、再帰関数の大きなOはO（n * log（n））です。