왜 수학 기초부터 다시 정리하는가

알고리즘 과목의 복잡도 계산은 결국 “반복문이 몇 번 도는가”를 수식으로 세는 작업이다. 이 수식을 세우고 정리하려면 로그·지수·팩토리얼이 무엇이고 서로 어떻게 다른 속도로 커지는지, 그리고 여러 항을 더하는 식(시그마)과 여러 항을 곱하는 식(파이)을 읽고 계산할 수 있어야 한다. 이 개념들은 03편(점근적 표기)부터 시작해 이 시리즈 전체에서 계속 쓰이는 공용 언어이므로, 여기서 확실히 정리해 두면 이후 각 편에서 “이 기호가 뭐였지”하고 멈추는 일이 없어진다.

쉽게 말하면: 이 편은 복잡도 계산에 필요한 “숫자 다루는 도구 상자”를 미리 챙기는 편이다.

함수와 수열 — 입력 크기에 따라 값이 달라진다는 것

함수(function)는 하나의 입력값에 하나의 출력값을 대응시키는 규칙이다. 알고리즘 분석에서는 주로 입력 크기 n(배열의 원소 개수, 그래프의 정점 수 등)을 입력값으로 받아, 연산 횟수나 사용 메모리량을 출력값으로 내놓는 함수를 다룬다. 예를 들어 “배열 원소를 한 번씩 출력하는 연산 횟수는 f(n) = n이다”라고 말할 때, f가 바로 이런 함수다.

수열(sequence)은 자연수 1, 2, 3, ...을 입력으로 받는 함수를 순서대로 나열한 것이다. 예를 들어 “정렬 알고리즘이 원소 하나를 처리할 때마다 비교 횟수가 1, 2, 3, ..., n-1처럼 늘어난다”고 표현할 때 이 나열이 수열이다. 함수와 수열을 구분하는 이유는, 알고리즘의 반복 횟수를 셀 때 “몇 번째 단계에서 몇 번 실행되는가”를 수열로 나타내고, 그 수열의 전체 합을 구해 전체 연산 횟수(하나의 함수 값)로 정리하는 흐름을 자주 쓰기 때문이다.

로그(log) — 몇 번 나눠야 1이 되는가

로그(logarithm, 줄여서 log라고 쓰고 “로그”라고 읽는다)는 “어떤 수를 몇 번 곱해야 원하는 값이 되는가”를 나타내는 연산이다. 알고리즘에서는 반대로 “어떤 수를 몇 번 나눠야 1이 되는가”로 이해하는 것이 더 직관적이다.

• log: 로그 기호. 아래 첨자(밑, base)로 몇을 거듭제곱하는 기준인지 표시한다.
• 2 (밑, base): 몇을 거듭제곱하는가. 알고리즘에서는 보통 절반씩 나누는 과정(이진 탐색, 병합 정렬의 분할)을 다루므로 밑이 2인 로그가 압도적으로 많이 쓰인다.
• n: 로그의 진수(대상 값). 여기서는 입력 크기를 뜻한다.
• k: 로그의 결과값. “2를 몇 번 곱해야 n이 되는가”의 답.

예를 들어 n = 8이면 2를 3번 곱하면(2 × 2 × 2 = 8) 8이 되므로 log₂8 = 3이다. 이것을 “8을 절반씩 3번 나누면 1이 된다(8 → 4 → 2 → 1)“로 바꿔 읽을 수 있다. 이 “절반씩 나누는 횟수”가 바로 이진 탐색이나 병합 정렬 같은 알고리즘의 복잡도가 O(log n)이 되는 이유의 뿌리다(자세한 유도는 04편과 07편에서 다룬다).

밑이 달라도 알고리즘 분석에서는 상수 배 차이일 뿐이다. 로그의 밑 변환 공식은 다음과 같다.

1 / log₁₀2는 그냥 하나의 상수(약 3.32)이므로, log₂n과 log₁₀n은 상수 배만큼만 차이가 난다. 앞으로 배울 Big-O 표기법(03편)에서는 상수 배 차이를 무시하므로, O(log n)이라고 쓸 때는 밑을 굳이 표시하지 않아도 된다.

자주 틀리는 점: “로그의 밑이 다르면 복잡도도 다르다”고 착각하는 경우가 있다. 하지만 밑이 무엇이든 로그 함수들끼리는 서로 상수 배 관계이므로, Big-O 표기에서는 log₂n이든 log₁₀n이든 그냥 O(log n)으로 쓴다.

지수(exponential) — 곱하는 횟수가 커질수록 폭발적으로 커진다

지수(exponential)는 2ⁿ처럼 어떤 수를 밑으로 하고 n을 지수(거듭제곱하는 횟수)로 쓰는 형태다. 로그가 “몇 번 나눠야 1이 되는가”였다면, 지수는 정반대로 “1에서 시작해 n번 곱하면 얼마나 커지는가”를 나타낸다.

n이 하나 늘어날 때마다 값이 두 배로 뛴다는 것이 지수 함수의 핵심 특징이다. 2¹⁰ = 1024인데 2²⁰은 1024의 제곱이 아니라 2¹⁰ × 2¹⁰ = 1,048,576으로, n이 10에서 20으로 두 배 늘었을 뿐인데 값은 약 1,000배가 된다. 알고리즘 분석에서 지수 시간(O(2ⁿ))이 “사실상 계산 불가능”으로 취급받는 이유가 여기 있다. n = 30만 되어도 2³⁰은 약 10억을 넘어선다.

팩토리얼(!) — 순서를 고려한 모든 경우의 수

팩토리얼(factorial, 느낌표 !로 표기하고 “n 팩토리얼”이라고 읽는다)은 1부터 n까지의 모든 자연수를 곱한 값이다.

예를 들어 5! = 5 × 4 × 3 × 2 × 1 = 120이다. 팩토리얼은 “서로 다른 n개의 물건을 한 줄로 세우는 방법의 수(순열)“를 셀 때 나온다. 알고리즘에서는 17편에서 다루는 백트래킹의 순열 생성 문제(n개를 일렬로 배열하는 모든 경우를 탐색)에서 팩토리얼 크기의 탐색 공간이 등장한다. 팩토리얼은 지수보다도 훨씬 빠르게 커지므로(10! = 3,628,800으로 2¹⁰ = 1024보다 훨씬 크다), 팩토리얼 크기의 완전 탐색은 n이 조금만 커져도 현실적으로 계산할 수 없다.

성장 속도 실제 숫자로 비교하기

로그, 선형(n), 로그선형(n log n), 이차(n²), 지수(2ⁿ), 팩토리얼(n!)이 얼마나 다른 속도로 커지는지 n = 10과 n = 20일 때 값을 직접 계산해 비교해 보자.

n이 겨우 두 배(10 → 20)로 늘었을 뿐인데, log n은 30퍼센트 정도만 커지지만 n!은 자릿수 자체가 완전히 달라진다. 이 표에서 확인할 수 있는 성장 속도 순서는 다음과 같다.

이 순서는 03편에서 배울 Big-O 표기법으로 알고리즘의 효율성을 비교할 때 그대로 쓰이는 기준이 된다.

쉽게 말하면: 오른쪽으로 갈수록 “n이 조금만 커져도 감당 못 할 만큼” 값이 폭발적으로 늘어난다.

시그마(Σ) — 여러 항을 더하는 기호

시그마(Σ, 그리스 대문자 시그마이며 “합”을 뜻하는 Sum의 첫 글자와 모양이 비슷해 합계를 나타내는 기호로 쓰인다)는 여러 항을 차례로 더한다는 것을 짧게 표현하는 기호다.

• Σ: “다음에 오는 식을 더하라”는 뜻의 기호.
• i = 1 (아래 첨자): 더하기를 시작하는 값. i를 1부터 시작한다는 뜻.
• n (위 첨자): 더하기를 끝내는 값. i가 n이 될 때까지 더한다.
• i (시그마 오른쪽 식): 실제로 더할 대상. 여기서는 i를 그대로 더한다.

알고리즘 분석에서 시그마는 “반복문이 매 단계 몇 번씩 도는지”를 그대로 더하는 데 쓰인다. 예를 들어 어떤 알고리즘이 i번째 단계에서 i번 연산을 한다면, 전체 연산 횟수는 i를 1부터 n까지 더한 값, 즉 위 식으로 정확히 표현된다.

기본 합 공식 — 외우지 말고 유도해서 검산하는 습관

이 공식은 독일 수학자 가우스가 어릴 때 1부터 100까지 순서대로 더하는 대신, 처음 항과 마지막 항을 짝지어(1+100, 2+99, …) 빠르게 계산했다는 일화로 유명하다. 짝을 지으면 (1+n)이 총 n/2쌍 나오므로, 합은 (1+n) × n / 2, 즉 n(n+1)/2가 된다.

n = 5로 직접 검산해 보자. 왼쪽은 1+2+3+4+5 = 15이고, 오른쪽은 5 × 6 / 2 = 15로 정확히 일치한다.

이 시리즈에서 특히 자주 쓰이는 합 공식을 정리하면 다음과 같다.

세 번째 공식은 04편에서 재귀 트리를 그려 병합 정렬의 복잡도를 유도할 때 그대로 다시 쓰이므로, 여기서 형태를 눈에 익혀 두면 도움이 된다.

파이(Π) — 여러 항을 곱하는 기호

파이(Π, 그리스 대문자 파이이며 “곱”을 뜻하는 Product의 첫 글자와 모양이 비슷해 곱셈을 나타내는 기호로 쓰인다)는 시그마의 “곱셈 버전”이다.

시그마가 +로 항을 연결한다면 파이는 ×로 항을 연결한다. 위 식에서 볼 수 있듯, 1부터 n까지를 파이로 곱한 결과가 바로 앞서 배운 팩토리얼(n!)이다. 파이 기호는 알고리즘 시리즈 안에서 시그마만큼 자주 등장하지는 않지만, 순열의 경우의 수를 수식으로 표현하거나(17편 백트래킹의 순열 생성 문제) 확률을 다루는 일부 심화 설명에서 등장할 수 있으므로 읽는 법만은 정확히 알아 두어야 한다.

자주 틀리는 점: Σ와 Π를 혼동해 “시그마인데 곱하는 것”, “파이인데 더하는 것”으로 잘못 읽는 경우가 있다. Σ는 덧셈(Sum), Π는 곱셈(Product)이라는 것을 영단어 첫 글자와 함께 기억하면 헷갈리지 않는다.

점근적 성장 비교를 위한 정리 — 이후 편으로 이어지는 다리

이 편에서 다룬 로그·지수·팩토리얼의 성장 속도 비교와 시그마 합 공식은 03편(점근적 표기와 시간·공간 복잡도)에서 바로 이렇게 쓰인다.

1. 반복문의 실행 횟수를 시그마 식으로 세운다.
2. 기본 합 공식으로 그 식을 정리한다(예: n(n-1)/2).
3. 정리된 식에서 최고차항만 남기고 상수를 지워 Big-O로 표현한다.
4. 로그·지수·팩토리얼의 성장 속도 순서를 기준으로 여러 알고리즘의 효율성을 비교한다.

이 흐름을 미리 알아 두면 03편의 유도 과정이 훨씬 자연스럽게 읽힌다.

자주 틀리는 점

• 로그의 밑을 다르게 계산해 결과가 달라진다고 착각하는 실수: 로그끼리는 상수 배 관계이므로 Big-O 표기에서는 밑을 구분하지 않는다.
• 지수와 팩토리얼을 비슷한 크기로 착각하는 실수: 같은 n에서 n!은 2ⁿ보다 항상 훨씬 크다(n이 4 이상일 때부터 확연히 벌어진다).
• 시그마의 시작 값을 확인하지 않는 실수: Σ(i=1 to n) i와 Σ(i=0 to n-1) i는 결과가 다르다(n(n+1)/2 vs n(n-1)/2). 아래 첨자의 시작 값을 항상 확인해야 한다.
• Σ와 Π를 혼동하는 실수: Σ는 덧셈, Π는 곱셈이다.

핵심 정리

• 로그는 “몇 번 나눠야 1이 되는가”, 지수는 “몇 번 곱하면 얼마나 커지는가”를 나타내며, 로그의 밑이 달라도 Big-O 표기에서는 상수 배 차이로 취급해 구분하지 않는다.
• 팩토리얼(n!)은 지수(2ⁿ)보다도 훨씬 빠르게 커지는 함수이며, 순열의 경우의 수를 셀 때 등장한다.
• 성장 속도 순서는 log n < n < n log n < n² < 2ⁿ < n!이며, 이 순서가 이후 알고리즘 효율성 비교의 기준이 된다.
• 시그마(Σ)는 여러 항의 합, 파이(Π)는 여러 항의 곱을 나타내는 기호이며, Σ(i=1 to n) i = n(n+1)/2는 이 시리즈에서 가장 자주 쓰이는 합 공식이다.
• 반복문의 실행 횟수를 시그마 식으로 세우고 합 공식으로 정리하는 흐름이 이후 복잡도 유도(03편)의 표준 절차가 된다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 알고리즘 과목 평가영역 중 복잡도 분석에 필요한 수학적 기초의 출제 수준을 확인하는 데 참고했다.
• Big-O Cheat Sheet  — 로그·선형·이차·지수 등 대표 복잡도 함수의 성장 속도를 시각적으로 비교해 볼 수 있는 공개 참고 자료.