再帰とBig Oで混乱している

Question

私は知っている T（n）= T（n/2）+θ（1）はO（ログN） の結果になる可能性があり、私の本はバイナリ検索。 しかし、あなたはそれをどのように知っていますか？バイナリサーチが問題を毎回半分にカットするので、それはO（ログN）なのでしょうか？

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

アルゴリズムが毎回半分に分かれていると、結果はO（N）であり、O（Log N）ではないのはなぜですか。

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

はO（N Log N）になる可能性がありますか？私はO（N）がθ（n）から来てO（Log N）がT（n/2）から来ているのを見ています

私は実際にはないアルゴリズムのBig Oそれを正しく語る方法さえ知っています。私の質問が理にかなったことを願っています。

ありがとうございます！

Answer 1

、これらの問題のための直感的な解決策は、再帰式を展開する場合、結果を確認することです。

のは、シータは、（1）実際には1であるとシータ（n）はシンプル

T(n) = T(n/2) + 1 = T(n/4) + 1 + 1 = T(n/8) + 1 + 1 + 1 = ... = 
= T(0) + 1 + ... + 1 [logN times] = logn 

T'(n) = 2T'(n/2) + 1 = 2(2T'(n/4) + 1) + 1 = 4T'(n/4) + 2 + 1 = 
= 8T'(n/4) + 4 + 2 + 1 = ... = 2^(logn) + 2^(logn-1) + ... + 1 = n + n/2 + ... + 1 = 
= 2n-1 

T''(n) = 2T(n/2) + n = 2(2T''(n/2) + n/2) + n = 4T''(n/4) + 2* (n/2) + n = 
= 8T''(n/8) + 4*n/4 + 2*n/2 + n = .... = n + n + .. + n [logn times] = nlogn 

のために、n個であると仮定してみよう

これらの式を正式に証明するには、inductionを使用してください。 T(n/2) = Xと仮定し、それを使用する - T(n) = Yを期待どおりに証明してください。 【T(n) = T(n/2) + 1】第式ための例示について

、 - 塩基はT(1) = 0
Baseが自明であると仮定= 1
任意k <= n-1ためT(n) <= lognを想定し、k = n
T(n) = T(n/2) + 1 <= (induction hypothesis) log(n/2) + 1 = log(n/2) + log(2) = log(n/2*2) = log(n)

Answer 2

のためにそれを証明するnについて成り立ちます

これらを理解する簡単な方法は、アルゴリズムが再帰の各ステップで費やす時間を考慮して合計時間を求めることです。まず、考慮しましょう。

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

ここで、n = 64です。

T(64) = T(32) + 1 ... 1 so far 
T(32) = T(16) + 1 ... 2 so far 
T(16) = T(08) + 1 ... 3 so far 
T(08) = T(04) + 1 ... 4 so far 
T(04) = T(02) + 1 ... 5 so far 
T(02) = T(01) + 1 ... 6 so far 
T(01) = 1   ... 7 total 

アルゴリズムが各ステップで「1」時間かかることがわかります。そして、各ステップが入力を半分に分割するので、総仕事はアルゴリズムが入力を2つに分割しなければならなかった回数です。これはlog2 nです。

次は、物事を簡単にするために、我々はT（1）= 1のベースケースから構築でしょう、しかし

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

場合を考えてみましょう。

T(01) = 1   ... 1 so far 

今、私たちはそう

T(02) = 2T(01) + 1 ... (1*2)+1 = 3 

、二回T（01）を行い、その後、1を追加する必要があります今、私たちは二度T（02）を行う必要があり、その後、1を追加し、そう

T(04) = 2T(02) + 1 ... (3*2)+1 = 7 
T(08) = 2T(04) + 1 ... (7*2)+1 = 15 
T(16) = 2T(08) + 1 ... (15*2)+1 = 31 
T(32) = 2T(16) + 1 ... (32*2)+1 = 63 
T(64) = 2T(32) + 1 ... (65*2)+1 = 127 

ここでアルゴリズムは127の仕事をしました。これは入力に定数（2）を乗算し、プラス定数（-1）にO（n）を掛けたものです。基本的に、この再帰は2に合計する無限のシーケンス（1 + 1/2 + 1/4 + 1/8 + 1/16）に対応します。

このメソッドをT（n）= 2T 2）+ nとそれがあなたにとってより意味があるかどうかを見てください。再帰式のためにT（n）を見つけるために

Answer 3

一つの視覚的な解決策は、ツリーでそれをスケッチすることです：
あなたのケースでは T(n) = number of nodes * time specified on each node.

T(n) = 2T(n/2) + 1
私はノード自体にthe oneを書いて、それを拡張します2つのノードへT(n/2)
注：T(n/2) = 2T(n/4) + 1と同じですが、やはり同じことをします。

  T(n) + 1 
     /  \  
     T(n/2)+1  T(n/2)+1 
    / \   / \ 
T(n/4)+1 T(n/4)+1 T(n/4)+1 T(n/4)+1 
... ... .. ..  .. .. .. .. 
T(1) T(1) .......... ............T(1) 

このツリー内のノードの数に等しいそして

2*height of tree = 2*log(n) = n 

T(n) = n * 1 = n = O(n)