算法效率；增长函数和 Big-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

我不确定确切的增长函数，但它看起来像 log(n) + C；其中 C = 执行“else”分支的次数。这里的任何帮助都会很棒!我为此绞尽脑汁太久了，没有用......

Answer 1

这看起来像是家庭作业，所以我会保持简短的回答。

我认为你应该尝试证明输入的 else 分支小于或等于另一个分支(每次你有一个奇数 k 并从中减去一个，你得到一个偶数)。然后证明第一个分支是log(n)，所以第二个分支必须小于或等于log(n)，并且2*log(n) 也是log(n)...