# 계산 복잡도와 Big-O 표기법

#### 이론적 배경

계산 복잡도는 알고리즘이나 수치해석 기법을 수행할 때 요구되는 연산 횟수나 메모리 사용량을 측정하는 개념이다. 복잡도가 낮다는 것은 대규모 문제에서도 빠르고 효율적으로 계산을 수행할 수 있음을 의미한다. 특히 수치해석에서는 반복 계산을 많이 수행하거나, 대규모 행렬 연산을 포함하는 경우가 많으므로 계산 복잡도에 대한 이해가 필수적이다.

알고리즘이 처리해야 하는 입력의 크기를 $n$이라 할 때, 복잡도를 정의하는 가장 흔한 방식은 $n$이 커질 때 알고리즘의 연산 횟수(또는 실행 시간)가 어떻게 변화하는지를 살펴보는 것이다. 이때 시간 복잡도와 공간 복잡도의 두 측면으로 나누어 고찰한다. 시간 복잡도는 알고리즘이 문제를 해결하기 위해 요구하는 전체 연산 횟수, 즉 반복문이나 조건문이 실행되는 횟수 같은 것을 반영한다. 공간 복잡도는 문제 해결을 위해 추가로 필요한 메모리 크기를 나타낸다.

예를 들어 $n$차원 벡터 $\mathbf{x}$와 $\mathbf{y}$의 내적을 계산하는 알고리즘을 생각하면, 내적 계산은

$$
\mathbf{x} \cdot \mathbf{y}
$$

형태로 표현되며, $x\_i$와 $y\_i$의 곱셈 및 덧셈 연산이 $i=1$부터 $i=n$까지 반복된다. 이때 총 연산 횟수는 대략 곱셈 $n$회, 덧셈 $n-1$회이므로 총 $2n-1$번의 연산이 요구된다고 말할 수 있다. 이와 같이 연산 횟수를 직접 셈하거나, 반복 구조를 기반으로 추정하는 방식이 시간 복잡도를 구하는 대표적인 방법이다.

수치해석에서 흔히 마주하는 연산 중 하나는 행렬–벡터 곱이다. $n\times n$ 행렬 $\mathbf{A}$와 $n$차원 벡터 $\mathbf{x}$의 곱 $\mathbf{A}\mathbf{x}$를 구하려면, 각 행에 대해 벡터와의 내적을 구해야 한다. 행이 $n$개, 각 내적을 구하기 위해 필요한 곱셈 연산이 $n$개, 덧셈 연산이 $n-1$개라고 볼 때, 전체 연산 횟수는 곱셈 약 $n^2$, 덧셈 약 $n(n-1)$ 정도가 된다. 이렇게 계산된 총 연산 횟수는 대략 $2n^2-n$ 정도가 되는데, 결국 $n$이 매우 커질 때는 $O(n^2)$ 형태로 접근한다.

이러한 방식으로 다루는 ‘점근적 복잡도(Asymptotic Complexity)’는 $n$이 충분히 큰 경우의 계산 비용을 예측하기 위한 모델이다. 이는 수치해석에서 매우 중요한데, 간단한 연립방정식을 풀더라도 대규모 행렬 연산이 필요해지기 때문이다. 예컨대 고전적인 가우스 소거법(Gaussian Elimination)은 $n\times n$행렬에 대해 $O(n^3)$의 계산 복잡도를 갖는다. 그러나 이를 좀 더 빠르게 수행하는 변형된 알고리즘(예: Strassen 곱셈을 이용한 가우스 소거)이 존재하기도 하며, 때론 $O(n^3)$보다 약간 빠른 수준으로 개선할 수 있다.

#### Big-O, Big-Omega, Big-Theta

수치해석에서 흔히 쓰이는 점근적 표기법에는 Big-O, Big-Ω, Big-Θ 등이 있다. Big-O 표기법은 $n$이 커졌을 때 알고리즘의 상한(Upper Bound)을 표현하는 기법이다. 함수 $f(n)$과 $g(n)$에 대해, $f(n)$이 $O(g(n))$라는 것은 $n$이 충분히 클 때 $f(n)$이 $g(n)$에 비례한 선에서 억제됨을 의미한다. 이를 엄밀하게 쓰면, 어떤 양의 상수 $c$와 $n\_0$가 존재하여, 모든 $n \ge n\_0$에 대해

$$
|,f(n),| \le c,|,g(n),|
$$

을 만족한다면 $f(n) = O(g(n))$라고 한다.

Big-Ω 표기법은 점근적 하한(Lower Bound)을 표현한다. $f(n) = \Omega(g(n))$라 하면, $n$이 충분히 커졌을 때 $f(n)$이 $g(n)$ 이하로 떨어지지 않고 일정 비율 이상으로 유지됨을 뜻한다. 즉 어떤 $c'>0$와 $n\_0'>0$가 존재하여 모든 $n \ge n\_0'$에 대해

$$
|,f(n),| \ge c',|,g(n),|
$$

을 만족한다면 $f(n) = \Omega(g(n))$라 한다.

Big-Θ 표기법은 상한과 하한이 모두 일치하는 경우로, $f(n)$이 $g(n)$에 대해 점근적으로 동일한 수준의 성장을 보임을 표현한다. 즉 $f(n) = O(g(n))$이면서 동시에 $f(n) = \Omega(g(n))$일 때 $f(n) = \Theta(g(n))$라고 한다. 이 표기법은 가장 대표적인 표현 중 하나로, 알고리즘의 ‘정확한’ 점근적 차수를 나타낸다.

#### 실제 예시

수치해석에서 빈번히 사용하는 선형대수 알고리즘인 LU 분해나 QR 분해는 대체로 $O(n^3)$ 시간이 소요된다. 예컨대 LU 분해를 수행하기 위해서는 행렬의 대각 원소를 피벗(pivot)으로 잡아가며, 부분 행렬에 대해 일련의 소거 과정을 수행한다. 이 과정에서 필요로 하는 곱셈과 덧셈의 총 횟수가 대략 $n^3/3$ 수준이라는 것을 유도할 수 있으며, 점근적으로 $O(n^3)$로 표현한다.

빠른 행렬 곱 알고리즘인 Strassen 알고리즘은 $n^2.8074...$ 정도의 복잡도를 갖는다. 이는 고전적인 $O(n^3)$보다 빠른 것이지만, 실제 구현 시 상수 항이나 부가적인 메모리 사용이 크게 늘어날 수 있으므로, $n$이 어느 정도 커야 그 효과를 실감할 수 있다. 또한 이후에 발표된 Coppersmith–Winograd 알고리즘이나 그 변형들은 복잡도를 더욱 줄일 수 있지만, 이 역시 실제 구현 시 오버헤드가 상당하다.

여기에서 중요한 점은, Big-O 표기법은 문제 크기가 극단적으로 커지는 상황에서의 대략적인 상한만을 제공한다는 것이다. 작은 크기의 문제에서는 상수 항이나 숨겨진 낮은 차수 항들의 영향력이 크게 작용하기 때문에, 실제 실행 시간은 Big-O로만 예측하기 어렵다. 그럼에도 불구하고 수치해석에서 $O(n^3)$, $O(n^2)$, $O(n \log n)$ 등의 표기는, 알고리즘 선택 시 필요한 직관적 판단의 지침이 된다.

#### Krylov 부분공간 기법과 수렴률

대규모 희소 행렬에 대해 반복 해법을 설계할 때, Krylov 부분공간(Krylov Subspace) 기법을 활용하면 보다 빠른 수렴을 기대할 수 있다. 대표적으로 직교화(Orthogonalization)를 통해 잔차(residual)를 감소시키는 GMRES(Generalized Minimal Residual), 세미직교 과정을 거치는 BiCGStab(Bi-Conjugate Gradient Stabilized) 등 다양한 알고리즘이 제안되어 왔다. 이러한 기법은 $\mathbf{A}\mathbf{x}=\mathbf{b}$의 해를 구하기 위해, 잔차 벡터 $\mathbf{r}^{(k)}=\mathbf{b} - \mathbf{A}\mathbf{x}^{(k)}$를 반복적으로 갱신하면서 Krylov 부분공간

$$
\mathcal{K}\_m(\mathbf{A}, \mathbf{r}^{(0)}) = \mathrm{span}{\mathbf{r}^{(0)}, \mathbf{A}\mathbf{r}^{(0)}, \mathbf{A}^2\mathbf{r}^{(0)}, \dots, \mathbf{A}^{m-1}\mathbf{r}^{(0)}}
$$

위에서 해를 탐색한다. 이때 $\mathbf{A}^k\mathbf{r}^{(0)}$를 효율적으로 계산하기 위해서는 행렬–벡터 곱 연산을 빠르게 수행하는 기술이 핵심이며, 이 연산은 일반적으로 $O(n^2)$ 복잡도를 갖는다. 그러나 행렬이 특별한 구조를 가질 경우(대각 또는 밴드 구조, 희소성 등) $O(n)$ 또는 그 이하로도 구현할 수 있다.

Krylov 부분공간 기반의 방법들은 반복 수 $m$을 증가시키며 해를 점차 개선하되, $m$이 문제 크기 $n$보다 훨씬 작을 때에도 이미 충분한 근사해를 얻을 수 있다는 장점이 있다. GMRES의 이론적 시간 복잡도는 한 번의 반복마다 $O(n^2)$ 연산을 필요로 하고, 이를 $m$번 반복하므로 $O(m n^2)$가 된다. 하지만 특정 조건하에서 $m$이 비교적 작게 유지될 수 있다면, 사실상 $O(n^2)$보다 더 낮은 복잡도로 근사해를 구하는 것과 유사한 성능을 발휘한다. 이는 반복 과정에서 직교화(Arnoldi 과정)나 재직교화(reorthogonalization) 등에 수반되는 추가 연산을 어떻게 최소화하느냐, 혹은 사전조건자(preconditioner)를 적용해 수렴률을 높이느냐에 따라 크게 달라진다.

예를 들어 GMRES 알고리즘에서 잔차를 최소화하는 과정은 Arnoldi 분해(Arnoldi Decomposition)를 수행하며 얻어지는 직교 기저 $\mathbf{v}\_1, \mathbf{v}\_2, \dots, \mathbf{v}\_m$ 위에서 문제를 축소(reduction)하는 절차로 설명된다. 이 Arnoldi 과정 자체가 매 반복마다 직교화 연산을 수행하여 $O(mn)$ 정도의 추가 비용을 발생시키는데, $m$이 커지면 이러한 직교화 비용이 누적되면서 총복잡도가 $O(m^2 n)$으로 악화될 수도 있다. 이를 방지하기 위해 Restarted GMRES(GMRES($m$)) 같은 방식으로 일정 횟수($m$)가 지나면 잔여 기저를 폐기하고 새롭게 Arnoldi 과정을 시작하는 기법을 도입하기도 한다. 이처럼 실제 계산 복잡도는 알고리즘의 세부 옵션, 사전조건, 직교화 전략 등 여러 요소에 따라 달라진다.

#### 사전조건자와 복잡도

Krylov 기법과 같은 반복 해법에서 사전조건자(preconditioner)는 문제를 잘 조정(Preconditioning)하여 반복 횟수를 크게 줄여주는 역할을 한다. 사전조건자의 기본 개념은, 원래의 선형계

$$
\mathbf{A}\mathbf{x} = \mathbf{b}
$$

대신, 적절한 행렬 $\mathbf{M}^{-1}$을 곱해

$$
\mathbf{M}^{-1}\mathbf{A}\mathbf{x} = \mathbf{M}^{-1}\mathbf{b}
$$

형태로 바꿔서 해석하는 것이다. $\mathbf{M}$이 $\mathbf{A}$와 유사하되 보다 조건이 좋아(Condition Number가 낮아) 빠르게 수렴할 수 있도록 설계되면, 반복 횟수가 획기적으로 감소한다. 문제는 $\mathbf{M}^{-1}$과의 곱셈 비용이 지나치게 크면 전체 알고리즘 이점이 사라진다는 점이다. 따라서 사전조건자를 구축할 때, 일정한 연산량으로 빠르게 곱셈을 수행할 수 있도록 설계하는 것이 중요하다.

가장 간단한 사전조건자 중 하나로 대각 사전조건자(diagonal preconditioner)가 있다. 이는 $\mathbf{M}$을 $\mathbf{A}$의 대각 원소들만으로 구성하는 것이어서, 역행렬 구하기가 간단하고 곱셈 연산도 $O(n)$에 가능하다. 하지만 효과가 그다지 뛰어나지는 않다. ILU(Incomplete LU) 분해는 보다 발전된 형태의 사전조건자이며, 특정 희소 패턴만 유지해 간소화된 LU 분해를 구한 뒤 이를 사전조건에 활용한다. ILU에서 허용하는 외부 패턴에 따라 ILU(0), ILU(k), ILUT 등 변형이 존재하며, 사전조건자를 구축하는 데 $O(n^2)$ 이상의 연산이 들 수 있지만, 그 결과 반복 횟수가 크게 줄면 전체 계산 비용을 절감할 수 있다.

이와 유사하게 AMG(Algebraic Multigrid) 같은 다중 격자 기법을 사전조건자로 사용할 수도 있다. AMG는 계층적 스케일에서의 문제 구조를 자동으로 파악해, 상위 격자와 하위 격자를 오가며 빠르게 잔차를 줄이는 방법이다. 이러한 접근법의 복잡도는 문제 구조와 세부 구현에 따라 다르지만, $O(n)$에서 $O(n\log n)$ 수준의 이론적 스케일링을 달성할 수 있다고 알려져 있다. 다만 실제로는 격자 구성을 위한 상호작용 그래프를 생성하고, 적절한 강연결(strong connection)·약연결(weak connection) 기준을 설정하는 과정에서 복잡도가 증가할 수 있다. 따라서 선형 계산복잡도가 보장된다고 해도, 구현이나 데이터 구조 최적화 단계에서 많은 노력이 필요하다.

#### 메모리 사용량과 연산량의 상관관계

수치해석 알고리즘을 분석할 때, 단순히 연산 횟수만 추적하는 것으로는 충분치 않다. 현대의 컴퓨터 아키텍처에서, 메모리 계층 구조(캐시, 메인 메모리, 디스크 I/O 등)에 따라 실제 실행 속도가 크게 달라지기 때문이다. CPU에서 정점 연산(flops)을 처리하는 속도는 매우 빠른 반면, 메모리로부터 데이터를 읽어오는 속도는 상대적으로 느리다. 이 때문에 $O(n^3)$ 연산이라도 캐시 적중률이 높으면 의외로 빠르게 계산이 끝날 수 있고, 반대로 $O(n^2)$ 알고리즘이라 해도 랜덤하게 분산된 메모리에 자주 접근해야 한다면 성능이 크게 떨어질 수 있다.

희소 행렬–벡터 곱을 예시로 들면, 일반적으로는 $O(n)$ 또는 $O(n \log n)$ 정도로 구현이 가능하지만, 행렬의 스파스 패턴이 불규칙하면 각 행에 저장된 데이터를 여기저기서 읽어와야 한다. 이때 캐시 효율이 떨어져 실제 체감 성능은 훨씬 낮아질 수 있다. 반면에 블록 구조나 대각선이 주로 차지하는 밴드 구조처럼, 메모리에 일괄적으로 저장해도 참조 지역성이 확보되는 경우에는 계산이 매우 빨라진다.

이처럼 수치해석에서 주어진 문제의 크기가 커질수록, 빅-오(Big-O) 표기법은 단지 “이론적인” 성장률을 가늠하는 수단일 뿐, 실제 성능은 메모리 할당이나 데이터 구조 설계, 캐시 활용, 벡터화(vectorization), 병렬화 등에 의해 결정된다는 점을 반드시 인식해야 한다. 그래도 빅-오 표기는 문제 크기가 거대해지는 경우를 대비하여, 알고리즘 선택의 1차적 판단 근거를 제공한다. 특히 고차원 편미분방정식(PDE)을 수치적으로 풀 때, 격자 크기(노드 개수)가 급격히 늘어나므로, 비효율적인 $O(n^3)$ 방법과 상대적으로 효율적인 $O(n)$\~$O(n\log n)$ 방법 사이의 차이가 실질적으로 엄청날 수 있다.

#### FFT(빠른 푸리에 변환) 기반 알고리즘과 복잡도

신호처리나 스펙트럴 방법(Spectral Method) 기반의 수치해석에서는 푸리에 변환이 핵심 연산으로 등장한다. 고전적인 이산 푸리에 변환(DFT)을 직접 계산하려면 $n^2$ 정도의 연산이 필요하지만, FFT(Fast Fourier Transform)를 사용하면 이를 $O(n \log n)$ 연산으로 줄일 수 있다. 실제로 편미분방정식(PDE) 풀이에서도 사인·코사인 변환 등을 통해 경계 조건을 효율적으로 처리하거나, 스펙트럴 방법을 사용하여 고차 정확도를 확보할 수 있다.

이 과정에서 FFT의 복잡도가 $O(n \log n)$이 된다는 점은 큰 문제에서 특히 중요하다. 격자 크기가 $n$에서 2배로 커지면, FFT를 통한 연산량은 단순 2배가 아니라 $2n \log(2n)$으로 증가하므로 $n^2$처럼 급격히 커지지 않는다. 다만, 실제로는 2차원, 3차원 문제로 확장하면 격자 크기가 $n\_1 \times n\_2$, 혹은 $n\_1 \times n\_2 \times n\_3$ 형태가 되어, FFT에 필요한 전체 연산 횟수 역시 차원에 따라 곱셈 형태로 늘어나는 점을 고려해야 한다. 예를 들어 2차원 FFT에서 $n \times n$ 격자를 처리하려면 $O(n^2 \log n)$, 3차원 FFT에서 $n \times n \times n$ 격자를 처리하려면 $O(n^3 \log n)$이 될 수 있다.

병렬 컴퓨팅 환경에서도 FFT는 중요한 역할을 한다. FFT는 버터플라이(Butterfly) 네트워크 구조를 갖고 있어서, 데이터 교환(Shuffle) 패턴이 비교적 예측 가능하다는 특징이 있다. 이 때문에 병렬화가 용이한 편이지만, 프로세서 간 통신 비용을 최소화하려면 데이터 배치를 어떻게 하느냐가 매우 중요해진다. 예컨대 2차원 혹은 3차원 FFT를 병렬화할 때, 축별로 병렬 처리를 나누고, 각 단계에서 통신을 잘 묶어서 처리해야 높은 스케일링 효율을 낼 수 있다. 그렇지 않으면 통신 오버헤드와 동기화 지연이 증가하여, 실제 병렬 성능이 $O(n \log n)$을 유지하기 어려워진다.

#### 도메인 분할(Domain Decomposition) 기법과 복잡도

편미분방정식을 유한요소법(FEM), 유한차분법(FDM), 유한체적법(FVM) 등으로 풀 때, 해 영역(domain)을 여러 개의 서브도메인(subdomain)으로 분할하고, 각 서브도메인 문제를 부분적으로 해결한 뒤 접합부(Interface)에서 조건을 맞춰 전체 해를 구하는 방식을 자주 사용한다. 이를 도메인 분할 기법이라 하며, 평행(병렬) 처리에서 효율을 높이기 위해 활용된다.

도메인 분할 방식의 대표적인 알고리즘에는 슈바르츠(Schwarz) 방식, FETI(Finite Element Tearing and Interconnecting), BDDC(Balancing Domain Decomposition by Constraints) 등이 존재한다. 이러한 기법은 ‘큰 문제를 여러 작은 문제로 쪼개고, 각 문제를 독립적으로 반복해법(또는 직접해법)으로 풀면서, 인터페이스에서 경계 조건을 보정하는 절차’를 반복한다. 각 서브도메인의 크기가 $n\_s$ 정도이고, 서브도메인 개수가 $p$라면, 각각의 부분 문제는 $O(n\_s^\alpha)$ 정도의 연산이 요구된다고 볼 수 있다. 그러나 서브도메인 간 통신이나 인터페이스 처리가 추가로 발생하므로, 전체 복잡도는 $p \times O(n\_s^\alpha)$에 더해 통신·동기화 비용이 결정한다.

도메인 분할 기법은 병렬 컴퓨팅에서 선형 스케일링(입력 크기가 증가해도 프로세서 수에 비례해 처리 시간이 거의 일정하게 유지되는 것)을 달성하기 위한 중요한 전략이다. 각 서브도메인 문제의 독립성이 커질수록, 프로세서 간 교류가 줄고, 결국 높은 병렬 효율을 얻을 수 있다. 반면 인터페이스의 비율이 커지면, $\mathbf{A}\mathbf{x}=\mathbf{b}$ 형태의 전역 선형계로 재조립 시 발생하는 통신량이 커지고 반복 횟수가 늘어날 수 있다. 따라서 균등하게 서브도메인을 분할하되, 경계 면적(또는 경계 노드 개수)을 최소화하는 기법이 중요하다.

#### 다중(front) 직접 해법과 점근 복잡도

직접 해법에서도 도메인 분할 아이디어가 확장된 고급 알고리즘들이 존재한다. 예를 들어 대규모 희소행렬에 대해 ‘멀티프론탈(Multifrontal)’ 방법을 적용하면, 행렬을 블록 구조로 분할·정복하면서 순차적으로 소거를 수행한다. 이때 각 블록의 전방(front)에서 연산을 집중 처리하고, 완결된 블록을 배제하여(Eliminate) 다음 블록으로 넘어간다. 이러한 알고리즘은 일반 가우스 소거법과 동일한 $O(n^3)$이 아니라, 행렬이 갖는 특별한 그래프적 구조(대각 혹은 밴드, 트리 형태의 연결 등)에 따라 $O(n^{2})$, 혹은 그 이하로 복잡도를 낮출 수 있다.

예컨대 2차원 격자 구조를 기반으로 한 희소행렬은 대각선 근방에만 유의미한 원소가 분포하므로, 적절한 순서(예: Nested Dissection)를 택하여 소거하면 $O(n^{3/2})$ 수준의 연산으로 해결할 수도 있다. 3차원 격자의 경우에는 $O(n^2)$ 정도로 더 커진다. 이처럼 행렬이 어떻게 희소성이 분포되어 있는지, 분할 기법이 어떤 순서로 소거를 진행하는지에 따라 실제 복잡도가 매우 달라진다.

***

수치해석에서 ‘계산 복잡도와 Big-O 표기법’을 철저히 이해한다는 것은, 결국 문제 구조와 알고리즘 특징, 그리고 하드웨어 환경까지 다각도로 조망할 수 있다는 뜻이다. 이론적으로 $O(n^3)$, $O(n^2)$, $O(n \log n)$ 등의 점근 표기가 사용되지만, 실제로는 조건 수, 희소 패턴, 사전조건자, 도메인 분할, 병렬화 전략, 캐시 최적화, 고성능 블라스(BLAS) 라이브러리 활용 여부 등이 결정적인 영향을 미친다. 따라서 이러한 복잡도 이론은 최적의 알고리즘을 선택하기 위한 출발점일 뿐, 최종 결정 단계에서는 주어진 문제와 컴퓨팅 환경 모두를 고려해야 한다.