|
|
|
|
로그형 O(logN) 알고리즘 (사례 3)
|
|
■ 빠른 지수계산 함수
|
|
-------------------------------------------------------------
long
int Pow( long int X, unsigned int N)
{
if( N == 0
) return 1;
if(
N == 1 ) return X;
if(
IsEven( N )) return( Pow( X*X, N/2 ));
else
return( Pow( X*X, N/2 ) * X);
}
-------------------------------------------------------------
|
|
|
<trace>
곱하기
수행 6회
|
Pow(2, 64) → ① Pow(2*2,
32) → ② Pow(4*4, 16) → ③ Pow(16*16,
8)
→
④ Pow(256*256, 4) → ⑤ Pow(216*216,
2) → ⑥ Pow(232*232,
1)
|
- X64을 for loop(Pow = Pow * X)으로 계산하면 64회
곱하기 수행,
- 빠른 지수함수는 log26≒6회 수행으로 계산,
- 승수가 1020이면 1020회 곱셈을 해야 하므로 컴퓨터로
수행이 불가능하다.
- 그러나 빠른 지수함수는 20log10≒64회 수행으로
계산한다.
- 여기에서 알고리즘 분석의 필요성을 이해할 수
있다.
|
|
|
