Kwangmin Kim - 알고리즘 복잡도와 Big-O 표기법

1 알고리즘의 정의

알고리즘(Algorithm)이라는 단어는 9세기 페르시아 수학자 알-콰리즈미(Al-Khwarizmi)의 이름에서 유래했다.

알고리즘: 어떤 문제를 해결하거나 계산을 수행할 때 실행되는 명확한 명령문의 유한한 나열

수학과 컴퓨터 과학에서 특정 문제들을 해결하거나 계산을 수행하는 데 사용되는 엄밀하고 유한한 명령의 연속
계산, 데이터 처리, 자동 추론의 명세로 활용

알고리즘의 두 가지 핵심 조건:

조건	설명	예시
명확성(Rigorous)	명령이 모호해서는 안 된다	“적당히 정렬해라” ❌ / “인접한 두 원소를 비교해서 앞이 크면 교환해라” ✅
유한성(Finite)	언젠가는 반드시 끝나야 한다	무한히 실행되는 명령의 나열은 알고리즘이 아니라 버그

알고리즘의 실행 흐름:

초기 상태(initial state) + 초기 입력(initial input) →
유한한 수의 잘 정의된 연속적인 상태들을 거쳐 →
출력(output) 생성 + 종료 상태(final ending state) 도달

레시피 비유

알고리즘은 “재료를 넣으면(input) → 정해진 조리과정을 거쳐(processing) → 음식이 나오는(output)” 레시피와 같다.

2 알고리즘의 4가지 핵심 특징

알고리즘을 설계하거나 평가할 때 반드시 점검해야 할 4가지 특징이 있다.

특징	핵심 질문	위반 시 문제
입력과 출력	입력을 받아 결과를 반환하는가?	알고리즘의 역할 정의 불가
유한성	반드시 종료되는가?	무한 루프 → 서버 장애
정확성	올바른 결과를 반환하는가?	빠르지만 틀린 알고리즘은 쓸모없음
효율성	빠르고 메모리를 적게 쓰는가?	실용적으로 사용 불가

2.1 입력과 출력 (Input & Output)

알고리즘은 반드시 입력값을 받아 처리하고, 결과를 출력으로 반환해야 한다
알고리즘의 성능은 입력 데이터에 비례 — 입력 크기가 커질수록 소비 시간과 자원도 증가
이것이 나중에 다룰 복잡도(complexity) 개념의 출발점

노트

입력이 없는 알고리즘도 존재한다(예: 항상 동일한 값을 반환하는 상수 함수). 그러나 실용적인 알고리즘의 대부분은 입력의 종류와 크기에 따라 결과가 달라지기 때문에, 입출력 관계를 정확히 정의하는 것이 알고리즘 설계의 첫 단계다.

2.2 유한성 (Finiteness)

알고리즘은 반드시 유한한 단계(finite steps)를 거쳐 종료되어야 한다
무한 루프(infinite loop)에 빠진 프로그램은 정의상 알고리즘이 아니다

실무에서의 중요성:

무한 루프 → 서버 자원 고갈 → 서비스 장애 유발
알고리즘이 반드시 끝나는지 증명하는 행위 = 종료 증명(termination proof)
재귀 알고리즘이나 복잡한 반복 조건에서 종료 조건을 명확히 설계하지 않으면 무한 루프 발생 가능

2.3 정확성 (Correctness)

알고리즘은 주어진 입력값에 대해 정확한 결과를 반환해야 하고, 원하는 목표를 달성해야 한다
빠르게 실행되지만 틀린 답을 반환하는 알고리즘은 아무 쓸모가 없다

정확성의 두 가지 측면:

유형	정의
부분 정확성(Partial Correctness)	알고리즘이 종료된다면, 그 결과가 올바른가?
완전 정확성(Total Correctness)	반드시 종료되고(유한성) + 결과가 올바른가(부분 정확성)?

실무적으로는 단위 테스트(unit test) 와 엣지 케이스(edge case) 검증이 정확성을 담보하는 주요 수단

2.4 효율성 (Efficiency)

가능한 빠르게(시간 효율) + 가능한 적은 메모리 사용(공간 효율)
정확하게 동작하더라도 10억 개의 데이터를 정렬하는 데 며칠이 걸리면 실용적이지 않다

효율성 측정 방식:

절대적인 수치(예: 몇 초)로 표현하지 않음 — 실행 환경(하드웨어, OS, 언어)에 따라 다르기 때문
Big-O 표기법이라는 추상적 척도로 효율성을 표현 (Part 2에서 상세 다룸)

3 왜 알고리즘을 공부해야 하는가

이유	핵심 가치
문제 해결 능력	체계적 분해 + 단계별 해결 사고방식 훈련
효율적인 프로그래밍	“동작하지만 느린” 코드를 방지
문제 예측과 예방	코드 작성 전 병목 지점 사전 파악
프로그래밍 언어 이해	내장 함수의 동작 원리와 선택 기준 파악
면접과 채용	테크 기업 기술 면접의 핵심 평가 항목

3.1 문제 해결 능력

특정 코드 패턴을 암기하는 것이 아니라, “주어진 문제를 체계적으로 분해하고 단계별로 해결하는 사고 방식” 을 훈련하는 것
예: “사용자 목록에서 특정 사용자를 찾아라”는 문제가 주어졌을 때 고려할 사항:
- 데이터를 어떻게 구성할 것인지 (정렬 여부)
- 어떤 탐색 방식을 쓸 것인지 (선형 탐색 vs 이진 탐색)
- 데이터 크기가 커질 때 성능이 어떻게 변할 것인지

3.2 효율적인 프로그래밍

알고리즘 지식 없이도 프로그램은 만들 수 있지만, 알고리즘을 모르면 “동작하지만 느린” 코드를 반복 작성
대표 사례: 중첩 반복문 남용
- 10만 개 데이터를 이중 for문으로 처리 → 100억 번 연산
- 해시 테이블 활용 시 → 10만 번 연산으로 해결
- 개인 프로젝트에서는 체감하기 어려우나, 수백만 사용자 서비스에서는 서버 비용과 응답 속도에 직결

3.3 문제 예측과 예방

“이 구조로 개발하면 데이터가 늘어날수록 성능이 급격히 저하될 것이다” 를 사전에 파악하고 설계를 바꾸는 능력
코드를 작성하기 전에 병목(bottleneck)을 미리 예측하는 것이 시니어 개발자와 주니어 개발자의 실질적인 차이 중 하나

3.4 프로그래밍 언어 이해

Python의 list.sort(), Java의 Collections.sort() 같은 내장 함수들은 이미 최적화된 알고리즘(예: Python의 Timsort)을 기반으로 구현
알고리즘을 이해하면:
- 내장 함수가 왜 그렇게 동작하는지 이해
- 어떤 상황에서 어떤 함수를 써야 하는지 판단 가능
- 언어의 표면적인 문법 너머를 볼 수 있는 렌즈 역할

3.5 면접과 채용

Google, Meta, 카카오, 라인 등 대부분의 테크 기업 기술 면접에서 알고리즘 문제 풀이를 핵심 평가 항목으로 포함
평가 목적: 단순히 코드를 짤 수 있는지가 아니라, 복잡한 문제를 논리적으로 분해하고 효율적인 해법을 도출하는 능력 평가
알고리즘 훈련 = 문제 해결 사고력의 훈련

4 정리

Part 1 핵심 요약

알고리즘: 명확하고 유한한 명령의 나열로 문제를 해결하는 구조
4가지 특징: 입출력, 유한성, 정확성, 효율성 — 좋은 알고리즘의 판별 기준
공부 이유: 문제 해결 사고력 훈련, 효율적 코드 작성, 병목 예측, 언어 내부 이해, 취업 경쟁력

다음 파트에서는 알고리즘의 효율성을 수학적으로 표현하는 방법인 복잡도(Complexity)와 Big-O 표기법을 다룬다.

5 복잡도란 무엇인가

Part 1에서 알고리즘의 4가지 특징 중 하나로 효율성을 언급했다. 복잡도(Complexity)는 바로 그 효율성을 수학적으로 측정하고 표현하는 도구다.

복잡도의 두 가지 축:

복잡도 종류	측정 대상	핵심 질문
시간 복잡도(Time Complexity)	알고리즘 실행에 필요한 연산의 총량	입력 크기가 커지면 연산 횟수가 얼마나 증가하는가?
공간 복잡도(Space Complexity)	알고리즘 실행에 필요한 메모리의 총량	입력 크기가 커지면 메모리 사용량이 얼마나 증가하는가?

복잡도 ≠ 실제 실행 시간

“연산의 총량”이라고 했지만, 실제 시간(초, 밀리초)을 측정하는 것이 아니다.

같은 알고리즘이라도 Intel i9에서는 0.001초, 라즈베리파이에서는 0.1초 실행
하드웨어 성능, 운영체제, 컴파일러 최적화 등 외부 요인이 너무 많음
절대적인 시간으로 알고리즘을 비교하는 것은 의미가 없다

컴퓨터 과학의 접근: “입력 크기 n이 증가할 때, 연산 횟수가 어떤 비율로 증가하는가?” 를 측정 → 이것이 점근적 분석(asymptotic analysis)의 핵심 아이디어이며 Big-O 표기법의 철학적 기반

6 시간 복잡도

알고리즘이 수행하는 기본 연산(elementary operation)의 횟수를 세어 추정
각 기본 연산은 고정된 시간이 걸린다고 가정
핵심 개념: 입력 크기 n — “처리해야 할 데이터의 개수”

n의 예시: - 배열에서 특정 값 탐색 → n = 배열의 길이 - 두 행렬 곱셈 → n = 행렬의 차원

측정 기준 — 왜 최악의 경우(worst-case)인가:

기준	설명
최악의 경우(worst-case)	어떤 입력이 들어와도 성능이 그 이하로 떨어지지 않는다는 상한선(upper bound) 보장
평균 복잡도(average-case)	같은 크기의 모든 가능한 입력에 대한 평균 시간 — 시스템 설계에서는 잘 사용 안 함

힌트

실제 서비스에서 알고리즘은 수억 번 호출된다. 평균적으로 빠르지만 특정 입력에서 급격히 느려지는 알고리즘은, 그 “특정 입력”이 자주 들어오는 순간 서비스 전체가 마비된다.

7 공간 복잡도

공간 복잡도: 알고리즘을 실행하는 데 필요한 메모리 공간의 총량

공간 복잡도를 구성하는 두 가지 메모리:

메모리 유형	설명
입력 공간(input space)	알고리즘이 실행될 때까지 입력값이 차지하는 메모리
보조 공간(auxiliary space)	알고리즘이 실행되는 동안 추가로 사용하는 메모리

예시: - n개의 원소 배열 복사 → 추가로 n개 크기의 메모리 필요 → O(n) - 제자리 정렬(in-place sort) → 추가 메모리 거의 없음 → O(1)

실무 관점: - 현대 개발 환경: 메모리가 저렴해지면서 시간 복잡도에 더 집중하는 경향 - ML/임베디드 환경: 공간 복잡도가 여전히 핵심 제약 조건 - 예: GPT 추론 시 VRAM 부족 = 공간 복잡도가 한계를 초과한 사례

8 Big-O 표기법

Big-O 표기법: 알고리즘의 점근적 상한(asymptotic upper bound)을 표현하는 수학적 표기법

핵심 원칙: n이 아주 커질 때, 가장 지배적인 항(dominant term)만 남기고 나머지는 무시한다.

예시: 3n² + 5n + 100의 Big-O 분석

항	n = 1,000,000 일 때 값
`3n²`	3,000,000,000,000 (지배적)
`5n`	5,000,000
`100`	100

→ 3n²이 압도적 → 상수 계수 3 제거 → O(n²)

노트

상수 계수를 제거하는 이유: “하드웨어가 3배 빠르면 상수가 사라지는” 수준의 차이이기 때문. Big-O는 하드웨어에 독립적인 성장 패턴을 포착한다.

Big-O 성장 속도 (느린 순 → 빠른 순):

표기법	이름	대표 예시
`O(1)`	상수 복잡도	배열 인덱스 접근
`O(log n)`	로그 복잡도	이진 탐색
`O(n)`	선형 복잡도	배열 순회
`O(n log n)`	선형 로그 복잡도	합병 정렬, 힙 정렬
`O(n²)`	이차 복잡도	중첩 반복문, 버블 정렬
`O(2ⁿ)`	지수 복잡도	재귀적 피보나치
`O(n!)`	팩토리얼 복잡도	외판원 문제 완전 탐색

경고

O(n!): n이 20만 넘어도 현실적으로 실행 불가능. NP-hard 문제의 완전 탐색이 이에 해당.

9 복잡도를 바라보는 실용적 관점

Big-O가 낮다고 항상 좋은 것은 아니다

n이 작은 경우(예: n < 100), 상수 계수가 큰 O(n log n) 알고리즘보다 상수 계수가 작은 O(n²) 알고리즘이 실제로 더 빠를 수 있다.

→ Python의 Timsort가 이를 활용: 작은 배열에서는 삽입 정렬(O(n²)), 큰 배열에서는 합병 정렬(O(n log n))을 전략적으로 혼합

시간-공간 트레이드오프(Trade-off):

더 많은 메모리를 사용해서(공간 복잡도 증가) 계산 속도를 높이는(시간 복잡도 감소) 전략이 존재
대표 기법: 동적 프로그래밍의 메모이제이션 — 계산 결과를 메모리에 저장해 중복 계산 방지

10 정리

Part 2 핵심 요약

복잡도: 알고리즘 효율성을 하드웨어에 독립적으로 측정하는 추상적 척도
시간 복잡도: 연산 횟수의 성장 패턴 (주로 최악의 경우 기준)
공간 복잡도: 메모리 사용량의 성장 패턴
Big-O: 입력 크기 n이 매우 커질 때 가장 지배적인 항만 취해 성능 특성 표현
최악의 경우 기준: 실제 서비스에서 성능의 상한선을 보장하기 위함

다음 파트에서는 가장 자주 등장하는 복잡도 유형인 O(n), O(n²), O(log n)을 실제 코드와 함께 구체적으로 분석한다.

11 O(n) — 선형 복잡도

11.1 개념

입력 크기 n에 비례해서 연산 횟수가 선형으로 증가
n이 2배 → 연산 횟수 2배 / n이 10배 → 연산 횟수 10배
그래프: 원점에서 시작해 일정한 기울기로 우상향하는 직선

O(n)이 나타나는 패턴: - 배열을 처음부터 끝까지 한 번 순회할 때 - 최악의 경우 배열의 모든 원소를 확인해야 하는 선형 탐색(linear search) - 배열 복사 — n개의 원소를 새 배열에 하나씩 담으면 정확히 n번 연산

11.2 코드 분석

# O(n) 시간 복잡도의 알고리즘 예시: 리스트의 모든 요소 출력
def print_list_elements(lst):
    for element in lst:         # lst의 길이 n만큼 반복
        print(element, end=" ") # 각 반복마다 1번의 연산 — O(1)
    print()                     # 반복 종료 후 1번 연산 (상수항, Big-O에서 무시)

복잡도 분석:

구성 요소	분석
`for element in lst`	n번 반복 → O(n) 결정
루프 내 `print`	O(1) 연산 × n번 = O(n × 1)
마지막 `print()`	1번만 실행 → O(1), 상수항 제거
시간 복잡도	O(n + 1) = O(n)
공간 복잡도	`element` 변수 하나만 추가 → O(1)

12 O(n²) — 이차 복잡도

12.1 개념

입력 크기의 제곱에 비례해서 연산 횟수 증가
n이 2배 → 연산 횟수 4배 / n이 10배 → 100배
그래프: 처음에는 완만하다가 n이 커질수록 가파르게 위로 꺾이는 포물선

실제 규모 비교:

n	O(n) 연산 횟수	O(n²) 연산 횟수
100	100	10,000
1,000	1,000	1,000,000
10,000	10,000	100,000,000

O(n²)이 나타나는 패턴: - 중첩된 반복문(nested loop) — 바깥 루프 n번 × 안쪽 루프 n번 = n²번 - 버블 정렬, 삽입 정렬, 선택 정렬이 모두 이 패턴

12.2 코드 분석

# 이차원 배열 표현
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# O(n²) 시간 복잡도의 알고리즘 예시: 모든 원소 출력
def print_matrix_elements(matrix):
    for row in matrix:          # 행(row) 수만큼 반복 — n번
        for element in row:     # 각 행의 열(column) 수만큼 반복 — n번
            print(element, end=" ")
    print()

복잡도 분석:

구성 요소	분석
바깥 루프	행의 수(n)만큼 반복
안쪽 루프	각 행의 원소 수(n)만큼 반복
총 연산 횟수	n × n = n²
시간 복잡도	O(n²)
공간 복잡도	추가 자료구조 없음 → O(1)

주의: 정방행렬 가정

이 예제는 n×n 정방행렬을 가정한다. 행의 수가 m, 열의 수가 n이라면 복잡도는 O(m×n)이다. 실무에서는 두 차원을 구분해서 분석해야 한다.

13 O(log n) — 로그 복잡도

13.1 개념

입력 크기가 증가해도 연산 횟수가 로그 함수처럼 완만하게 증가
log₂(n) = “n을 2로 몇 번 나눌 수 있는가”

로그의 위력:

n	log₂(n) (연산 횟수)
8	3
1,024	10
1,048,576 (약 100만)	20

→ n이 100만 배 커져도 연산 횟수는 20번에 불과

그래프: 초반에 빠르게 상승하다가 점점 완만해지는 곡선(concave curve)
O(n)의 직선과 비교: n이 커질수록 O(log n)이 O(n)을 압도적으로 앞섬

O(log n)이 나타나는 패턴: - 매 단계마다 탐색 범위를 절반으로 줄이는 것 - 이진 탐색(Binary Search), 균형 이진 트리(Balanced BST) 탐색이 대표적

13.2 코드 분석

def binary_search(arr, target):
    low, high = 0, len(arr) - 1  # 탐색 범위의 시작과 끝을 초기화

    while low <= high:
        mid = (low + high) // 2  # 현재 탐색 범위의 중간 인덱스 계산
        mid_value = arr[mid]     # 중간 인덱스의 값

        if mid_value == target:
            return mid           # 찾은 경우 해당 인덱스 반환
        elif mid_value < target:
            low = mid + 1        # 중간 값이 목표보다 작으면 오른쪽 반으로 탐색
        else:
            high = mid - 1       # 중간 값이 목표보다 크면 왼쪽 반으로 탐색

    return -1                    # 목표값이 배열에 없는 경우

O(log n)인 이유 — 매 반복마다 탐색 범위가 절반으로 줄어든다:

반복	동작	탐색 범위 (n=1,000,000)
1회	`mid_value < target` → `low = mid + 1` (왼쪽 절반 버림)	500,000
2회	`mid_value > target` → `high = mid - 1` (오른쪽 절반 버림)	250,000
3회	…	125,000
20회	…	약 1

복잡도 분석:

항목	분석
시간 복잡도	O(log n) — 최악의 경우 log₂(n)번 반복
공간 복잡도	`low`, `high`, `mid`, `mid_value` — 고정 변수만 사용 → O(1)

이진 탐색 전제 조건

배열이 반드시 정렬되어 있어야 한다. 정렬되지 않은 배열에 이진 탐색 적용 시 틀린 결과 반환.

데이터를 한 번 정렬하고 수백만 번 탐색 → 이진 탐색이 압도적으로 유리
탐색이 한 번뿐이라면 정렬 비용이 오히려 손해

14 세 복잡도의 비교

입력 크기 n	O(log n)	O(n)	O(n²)
10	3	10	100
100	7	100	10,000
1,000	10	1,000	1,000,000
1,000,000	20	1,000,000	1,000,000,000,000

노트

n = 1,000,000일 때 O(n²)의 연산 횟수는 1조(10¹²). 현대 CPU가 초당 약 10억 번 연산을 처리한다고 가정하면:

O(n²): 약 1,000초(약 17분) 소요
O(log n): 20번의 연산으로 끝

알고리즘 선택은 “코드 스타일의 취향”이 아니라 시스템의 생사를 결정하는 엔지니어링 결정이다.

15 정리

Part 3 핵심 요약

복잡도	패턴	성장 방식
O(n)	단일 루프, 배열 한 번 순회	입력 크기에 비례해 선형 증가
O(n²)	중첩 루프	입력 크기의 제곱으로 증가, 대용량 데이터에 불리
O(log n)	매 단계 탐색 범위를 절반으로 감소	입력이 아무리 커져도 완만하게 증가

다음 파트에서는 이 복잡도 지식을 바탕으로 버블 정렬과 삽입 정렬의 동작 원리와 코드를 분석한다.