※ 引述《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