정답
\(n = 15\)일 때 곱셈 연산 횟수는 (가) 알고리즘이 15회, (나) 알고리즘이 8회이다. (가)의 시간 복잡도는 \(O(n)\), (나)의 시간 복잡도는 \(O(\log n)\)이다.
출제 의도
같은 기능(입력 \(n\)에 대해 \(2^n\)을 계산)을 하는 두 알고리즘의 곱셈 연산 횟수를 비교하고, 반복 횟수에 따른 시간 복잡도를 점근 표기법으로 나타낼 수 있는지를 평가한다. 또한 지수 승을 단순 반복 곱셈으로 계산하는 방법과 이진 분해(제곱 반복)를 이용하는 방법의 효율성 차이를 이해하는지를 묻는다.
풀이 과정
(가) 알고리즘 POW1은 다음과 같이 동작한다.
초기값으로 \(p = 1\)에서 시작하여 반복문에서 \(i = 0\)부터 \(i = n-1\)까지 총 \(n\)번:
$$ p = p \times 2 $$
라는 곱셈을 한 번씩 수행한다. 따라서 곱셈 연산 횟수는 정확히 \(n\)회이다. \(n = 15\)일 때는
$$ \text{곱셈 횟수} = 15 $$
이다.
반면 (나) 알고리즘 POW2는 지수승을 이진 분해하여 계산하는 알고리즘이다. 코드 구조를 정리하면 다음과 같다.
초기값: \(d = 2,\; p = 1\) 반복: \(n > 0\)인 동안,
\(\quad\)만약 \(n \bmod 2 = 1\)이면 \(p = p \times d\) 수행 \(\quad d = d \times d\) 수행 \(\quad n = n \gg 1\) (즉, \(n\)을 2로 나눈 몫으로 갱신)
여기서 곱셈 연산은 두 가지이다.
1) 조건에 따라 수행되는 \(p = p \times d\) 2) 항상 수행되는 \(d = d \times d\)
\(n = 15\)일 때를 단계별로 추적하자. 15를 2진수로 나타내면
$$ 15 = (1111)_2 $$
이므로, 반복마다의 \(n\) 값과 곱셈 횟수를 표로 나타내면 다음과 같다.
1회전: \(n = 15\) (홀수) → \(p = p \times d\) 1회, \(d = d \times d\) 1회 → 총 2회 2회전: \(n = 7\) (홀수) → 곱셈 2회 누적 → 총 4회 3회전: \(n = 3\) (홀수) → 곱셈 2회 누적 → 총 6회 4회전: \(n = 1\) (홀수) → 곱셈 2회 누적 → 총 8회, 이후 \(n = 0\)이 되어 종료
따라서 (나) 알고리즘의 곱셈 연산 횟수는
$$ \text{곱셈 횟수} = 8 $$
이다.
이제 두 알고리즘의 시간 복잡도를 비교한다.
(가) 알고리즘은 반복문이 정확히 \(n\)번 수행되고, 각 반복에서 수행되는 연산은 상수 개이므로 전체 시간은 \(n\)에 비례한다.
$$ T_1(n) \propto n \quad \Rightarrow \quad T_1(n) = O(n) $$
(나) 알고리즘은 매 반복마다 \(n\)을 오른쪽 시프트(n = n >> 1)하여 절반으로 줄인다. 따라서 반복문은 대략 \(\log_2 n\)번 수행된다. 각 반복에서 곱셈 연산은 최대 2번으로 상수 개이므로 전체 시간은 \(\log n\)에 비례한다.
$$ T_2(n) \propto \log_2 n \quad \Rightarrow \quad T_2(n) = O(\log n) $$
결국 \(n\)이 커질수록 \(O(\log n)\)인 (나) 알고리즘은 \(O(n)\)인 (가) 알고리즘보다 곱셈 연산 횟수가 훨씬 적어지므로, (나) 알고리즘이 더 효율적이라고 할 수 있다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>