C++에서 O(log n)으로 복소수 거듭제곱 계산하기

x+yi 형태의 복소수와 정수 n이 주어졌을 때, 해당 복소수를 n제곱한 값을 계산해 출력하는 프로그램을 만들어 보겠습니다. 핵심은 단순 반복 방식(O(n))보다 빠른 O(log n) 시간 안에 답을 구하는 것입니다.

복소수란 무엇인가?

복소수(complex number)는 a+bi 형태로 표현되는 수입니다. 여기서 a와 b는 실수이며, i는 i² = −1을 만족하는 허수 단위입니다. 쉽게 말해 복소수는 실수부와 허수부가 결합된 수라고 할 수 있습니다.

복소수 거듭제곱의 원리

복소수를 거듭제곱하려면 먼저 두 복소수의 곱셈 공식을 알아야 합니다.

(a+bi)(c+di) = (ac − bd) + (ad + bc)i

예를 들어 복소수 2+3i를 5제곱한다고 하면 다음과 같이 표현할 수 있습니다.

(2+3i)⁵ = (2+3i)(2+3i)(2+3i)(2+3i)(2+3i)

위 공식을 반복해서 적용하면 최종적으로 (2+3i)⁵ = 122 − 597i라는 결과를 얻을 수 있습니다.

입력 · 출력 예시

입력: x[0] = 10, x[1] = -11  /* x[0]은 실수부, x[1]은 허수부 */
n = 4
출력: -47959 + i(9240)

입력: x[0] = 2, x[1] = 3
n = 5
출력: 122 + i(-597)

문제 해결 접근 방법

복소수를 n번 반복해서 곱하는 방법으로도 문제를 풀 수 있지만, 이 경우 시간 복잡도가 O(n)이 됩니다. 이를 개선하기 위해 지수를 매번 절반으로 줄여 가는 분할 정복(빠른 거듭제곱) 기법을 사용하면 O(log n)에 해결할 수 있습니다.

먼저 입력값을 배열 형태로 받습니다.
power 함수에서 xⁿ을 계산합니다.
- n이 0이면 0을 반환하고, n이 1이면 x를 그대로 반환합니다.
- power(x, n/2)를 재귀 호출한 뒤 그 결과를 변수 part에 저장합니다.
- n을 2로 나눈 나머지가 0이라면 cmul(part, part)를 반환합니다.
- n이 홀수라면 cmul(x, cmul(part, part))를 반환합니다.
cmul() 함수는 두 복소수의 곱을 처리합니다. x₁ = a+bi, x₂ = c+di일 때 x₁·x₂ = (ac − bd) + (bc + da)i 임을 이용합니다.
최종 결과를 반환하고 출력합니다.

알고리즘

시작
Step 1 -> 두 복소수의 곱을 계산하는 함수 선언
    long long* complex(long long* part1, long long* part2)
    long long* ans = new long long[2]
    ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1])
    ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1]
    return ans
Step 2 -> 복소수를 n제곱한 값을 반환하는 함수 선언
    long long* power(long long* x, long long n)
    long long* temp = new long long[2]
    IF n = 0
        temp[0] = 0
        temp[1] = 0
        return temp
    End
    IF n = 1
        return x
    End
    long long* part = power(x, n / 2)
    IF n % 2 = 0
        return complex(part, part)
    End
    return complex(x, complex(part, part))
Step 3 -> main() 함수 내
    int n 선언
    long long* x = new long long[2] 선언 및 초기화
    x[0] = 10
    x[1] = -11
    n = 4
    long long* a = power(x, n) 호출
종료

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 두 복소수의 곱을 계산하는 함수
long long* complex(long long* part1, long long* part2) {
    long long* ans = new long long[2];
    ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1]);
    ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1];
    return ans;
}
// 복소수를 n제곱한 값을 반환하는 함수
long long* power(long long* x, long long n) {
    long long* temp = new long long[2];
    if (n == 0) {
        temp[0] = 0;
        temp[1] = 0;
        return temp;
    }
    if (n == 1)
        return x;
    long long* part = power(x, n / 2);
    if (n % 2 == 0)
        return complex(part, part);
    return complex(x, complex(part, part));
}
int main() {
    int n;
    long long* x = new long long[2];
    x[0] = 10;
    x[1] = -11;
    n = 4;
    long long* a = power(x, n);
    cout << a[0] << " + i ( " << a[1] << " )" << endl;
    return 0;
}

실행 결과

O(Log n)으로 구한 복소수의 거듭제곱 : -47959 + i ( 9240 )

이처럼 지수를 매번 절반으로 나누어 재귀 호출하면 곱셈 연산 횟수가 log₂n 수준으로 줄어들기 때문에, n이 매우 큰 경우에도 복소수의 거듭제곱을 효율적으로 계산할 수 있습니다.