---

※ 引述《jengjian (賺錢花錢賺錢花錢)》之銘言：
: 解法三:
: for(i=0x80000000; i!=0; i=i>>1)
: {
:    sum <<= 1;
:    if(i&n)
:    {
:       sum += (1+n);
:    }
: }
: sum >>= 1;
: --
: 推 wzbird:我也覺得三在定義上不算"演算法" 只能說是寫程式的技巧      12/21 14:22
: → wzbird:不過或許業界定義的演算法跟書上的不盡相同吧               12/21 14:23
解法三確實是演算法
一個經典的例子是，計算 a**n (a 的 n 次方)
如果一般的解法
long ans=1;
for(int i=0; i<n; i++) {
        ans *= a;
}

時間複雜度是 O(n) ，如果 b 很大（譬如考慮大數），就很久

假設用 3**19 來說，因為 19 的二進位制是 10011

3**19  =   1 * 3**1
         + 1 * 3**2             3**2  = (3**1)**2
         + 0 * 3**4             3**4  = (3**2)**2
         + 0 * 3**8             3**8  = (3**4)**2
         + 1 * 3**16            3**16 = (3**8)**2

比較快的演算法為：
long ans=1;
long base=a;
for(; n>0; n/=2) {
        if(n%2==1) {
                ans*=base;
        }
        base=base*base;
}

時間複雜度是 O(log n)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.45

--