Iこのアルゴリズムから漸化式を見つけなければならないアルゴリズム

Question

から漸化式を探す：

ALGO(n) 
    if n <= 2 then return(0) 
    else 
     y = ALGO(n/3) 
     i = 2^n 
     while i >= 2 do 
      j = (1/2) * log(i) //base 2 
      while j > 0 do 
       i = i/2 
       j = j - 1 
     z = ALGO(n/2) 
     return(z+y) 

を私はそれについて推論と T（N）= O（1）= 2 <

N場合と結論づけ

内部whileはO（n）（各反復でjが1ずつ減っている）、外側whileはO（logn）（iは各反復で半分になります） n> 2の場合、T（n/3）+ T（n/2）+ O（n * log（n））：

これは良い議論ですか？

Answer 1

2つのループはO（N）であるべきである。

1. i = 2^n; 
2. j = (1/2) * log (i) = 1/2 * n = n/2 
3. the inner while executes for n/2 times then j becomes 0, now i = i/2^(n/2) = 2^(n/2); 

今、このプログラムは、私は半分だけで、ステップ1に戻ります。したがって、2つのループは次のようにする必要があります。

n/2+n/4+n/8+... = O(n) 

実際、これはより簡単な観点からも見ることができます。ループはi == 1になるまで終了せず、i = i/2の実行ごとに内部ループがn回実行されます。私たちが内側のループとoutループを平坦化すると仮定すると、i = i/2のn倍が存在するので、2つのループはO（n）です。 T（n）= T（n/3）+ T（n/2）+ O（n）となる。

これは役に立ちます。