アルゴリズムの効率。だからここに生長関数とビッグ-O表現

Question

は、アルゴリズムです：

Algorithm pow (a, n): 
Input: two integers, a (base) and n (exponent) 
Output: returns the equivalent of a^n 

K ← n 
b ← 1 
c ← a 

while k > 0 do 
    if k mod 2 = 0 then 
     k ← k/2 
     c ← c * c 
    else 
     k ← k − 1 
     b ← b * c 
return b 

私はわからないんだけど、それはログ（N）+ Cのように見える正確な成長関数。ここで、Cは「else」ブランチが実行された回数です。ここのどんな助けも素晴らしいだろう！私はこの上に私の頭を長持ちさせて長持ちしています...

Answer 1

これは宿題のように見えるので、私は答えを簡潔にしておきます。

私は、elseブランチが他のブランチと同じかそれより小さいかどうかを試してみるべきだと思います。（あなたが奇数kを持ち、そこから1を引くたびに偶数が得られます。最初のブランチがlog（n）であることを示し、2番目のブランチはlog（n）以下でなければならず、2 * log（n）もlog（n）です...