알고리즘의 시간 복잡도를 분석할 때, 반복문 내부 연산의 총 수행 횟수를 수학적으로 표현하는 것은 필수적입니다. 중첩 루프를 포함한 코드의 실행 시간을 평가할 때, 각 단계의 연산량을 누적하여 계산하는 방식이 널리 사용됩니다.

long long calculateComplexity(int n) {
    long long totalOps = 0;
    for (int row = 0; row < n; ++row) {
        for (int col = row + 1; col < n; ++col) {
            totalOps += row * col;
        }
    }
    return totalOps;
}

위와 같은 구조에서 내부 루프의 반복 횟수를 합산하면 전체 실행 시간이 이차 방정식 형태를 띠게 되며, 이는 점근적 표기법으로 $O(n^2)$으로 정리됩니다. 이러한 분석을 위해 먼저 합산($\sum$)과 곱셈($\prod$)의 수학적 정의와 성질을 이해해야 합니다.

합산(시그마) 표기법과 기본 성질

유한한 수열 $x_1, x_2, \dots, x_n$의 모든 항을 더하는 연산은 다음과 같이 표현됩니다.

$$ \sum_{i=1}^{n} x_i = x_1 + x_2 + \dots + x_n $$

$n=0$인 경우 합은 0으로 정의됩니다. 무한 수열의 경우 극한 개념을 도입하여 $\lim_{m \to \infty} \sum_{i=1}^{m} x_i$로 표현하며, 극한값이 존재하면 수렴, 존재하지 않으면 발산한다고 합니다.

선형성(Linearity)

합산 연산은 상수 곱셈과 덧셈에 대해 선형성을 가집니다. 임의의 상수 $c$와 수열 $\{x_i\}, \{y_i\}$에 대하여 다음 관계가 성립합니다.

$$ \sum_{i=1}^{n} c \cdot x_i = c \sum_{i=1}^{n} x_i $$

$$ \sum_{i=1}^{n} (x_i + y_i) = \sum_{i=1}^{n} x_i + \sum_{i=1}^{n} y_i $$

이 성질은 알고리즘 분석에서 점근적 표기법(예: $O(\cdot)$)을 포함한 항들을 통합할 때 유용합니다.

주요 급수 공식

• 등차급수(Arithmetic Series): 공차 $d$를 갖는 수열 $a, a+d, a+2d, \dots$의 합은 다음과 같습니다.

$$ S_n = \frac{n}{2} [2a + (n-1)d] $$

특히 $a=1, d=1$인 자연수 합의 경우 $\sum_{i=1}^n i = \frac{n(n+1)}{2}$입니다.

• 제곱수 및 세제곱수 합:

$$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}, \quad \sum_{i=1}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2 $$

• 등비급수(Geometric Series): 공비 $r \neq 1$인 수열 $a, ar, ar^2, \dots$의 합은 다음과 같습니다.

$$ S_n = a \frac{r^n - 1}{r - 1} $$

무한 등비급수의 경우 $|r| < 1$이면 $\sum_{i=0}^\infty r^i = \frac{1}{1-r}$로 수렴합니다.

• 조화급수(Harmonic Series): $H_n = \sum_{i=1}^n \frac{1}{i}$는 자연로그와 오일러-마스케로니 상수 $\gamma$를 사용하여 근사할 수 있습니다.

$$ H_n \approx \ln n + \gamma $$

이 근사식을 활용하면 아래 코드의 복잡도를 분석할 수 있습니다.

int countSteps(int n) {
    int steps = 0;
    for (int k = 1; k <= n; ++k) {
        for (int p = 0; p < n / (k + 1); ++p) {
            steps++;
        }
    }
    return steps;
}

내부 루프의 실행 횟수가 $n/(k+1)$에 비례하므로, 총 연산 횟수는 약 $\sum_{k=1}^n \frac{n}{k} = n H_n$이 되어 $O(n \log n)$의 시간 복잡도를 가집니다.

곱셈(파이) 표기법

유한 수열의 모든 항을 곱하는 연산은 다음 기호로 나타냅니다.

$$ \prod_{i=1}^{n} x_i = x_1 \times x_2 \times \dots \times x_n $$

$n=0$일 때 곱의 값은 곱셈의 항등원인 1로 정의됩니다.

값 계산 및 증명 기법

부분 분수 분해 및 상쇄(Telescoping)

항을 분해하여 인접한 항끼리 소거되는 구조로 변형하는 방법입니다. 다음 합계를 고려해 봅시다.

$$ \sum_{k=1}^{m} \frac{1}{(2k-1)(2k+1)} $$

항을 부분 분수로 분해하면 $\frac{1}{(2k-1)(2k+1)} = \frac{1}{2} \left( \frac{1}{2k-1} - \frac{1}{2k+1} \right)$입니다. 이를 대입하여 전개하면 중간항들이 모두 사라지고 다음과 같은 결과가 남습니다.

$$ \frac{1}{2} \left( 1 - \frac{1}{2m+1} \right) = \frac{m}{2m+1} $$

곱셈 형식에서도 동일한 원리가 적용됩니다. $\prod_{k=2}^{m} \frac{k^2-1}{k^2}$의 경우, 각 항을 $\frac{k-1}{k} \cdot \frac{k+1}{k}$로 인수분해하면 분자와 분모가 겹치는 부분이 상쇄되어 최종적으로 $\frac{m+1}{2m}$으로 정리됩니다.

수학적 귀납법(Mathematical Induction)

자연수 $n$에 대한 명제 $P(n)$이 모든 $n$에서 성립함을 보일 때 사용됩니다. 기본 단계($n=1$일 때 성립)와 귀납 단계($n=k$일 때 성립하면 $n=k+1$에서도 성립)를 확인합니다.

예를 들어, $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$임을 증명해 보겠습니다.

• 기본 단계: $n=1$일 때, 좌변 $= 1^2 = 1$, 우변 $= \frac{1(2)(3)}{6} = 1$. 성립합니다.
• 귀납 가정: $n=k$일 때 공식이 성립한다고 가정합니다.
• 귀납 단계: $n=k+1$일 때, $$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 $$ $$ = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} $$ $$ = \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6} $$ 이는 $n=k+1$을 공식에 대입한 형태와 일치하므로 명제가 증명됩니다.

급수의 경계(Bound) 추정 방법

정확한 합계값보다 상한 또는 하한을 구하는 것이 효율적인 경우가 많습니다.

항별 경계 적용

급수 $\sum_{i=1}^n x_i$의 각 항이 $x_i \le M$을 만족한다면, 전체 합은 $n \cdot M$ 이하입니다. 예를 들어 $\sum_{i=1}^n \sqrt{i} \le \sum_{i=1}^n \sqrt{n} = n\sqrt{n} = n^{1.5}$으로 상한을 설정할 수 있습니다.

단, 급수가 기하급수적으로 감소하는 경우(공비 $0 < q < 1$), 가장 큰 항인 첫 번째 항 $x_0$로 모든 항을 묶으면 $\sum_{i=0}^n x_i \le x_0 \sum_{i=0}^\infty q^i = \frac{x_0}{1-q}$로 더 tighten한 상한을 얻을 수 있습니다. 조화급수처럼 인접 항의 비가 1에 수렴하는 경우에는 이 방법이 유효하지 않으므로 주의해야 합니다.

구간 분할(Splitting)

합산 범위를 여러 구간으로 나누어 각각의 경계를 구한 뒤 합칩니다. 조화수 $H_n = \sum_{i=1}^n \frac{1}{i}$의 경우를 예로 들어みます.

구간을 $[2^j, 2^{j+1})$ 형태로 나누면, 각 구간 내의 항 개수는 $2^j$개이며, 각 항의 값은 최대 $\frac{1}{2^j}$입니다. 따라서 각 구간의 합은 최대 $2^j \cdot \frac{1}{2^j} = 1$입니다. 구간 수는 $\approx \log_2 n$개이므로, 전체 합은 $O(\log n)$으로 bounded 됩니다.

적분近似(Integral Approximation)

단조증가 함수 $f(x)$에 대하여, 합계는 적분으로 다음과 같이 양쪽에서 경계 지을 수 있습니다.

$$ \int_{m-1}^{n} f(x) \, dx \le \sum_{i=m}^{n} f(i) \le \int_{m}^{n+1} f(x) \, dx $$

이 기하학적 해석은 직사각형 넓이와 곡선 아래 넓이의 관계를 이용하여 유도됩니다. 단조감소 함수일 경우 부등호 방향이 반대가 됩니다. 이를 $f(x) = 1/x$에 적용하면 조화수 $H_n$이 $\ln(n+1) \le H_n \le \ln n + 1$ 범위에 있음을 확인할 수 있으며, 이는 알고리즘 분석에서 로그 항을 다루는 표준적인 접근법입니다.