알고리즘(Algorithm)

점근 표기법(Asymptotic notation)

입력 크기 n이 커질 때 걸음 수가 어떤 속도⁠(velocity)⁠로 자라는지를 상수배를 무시하고 적는 표기. O(n), O(n log n), O(n²), O(2ⁿ)의 차이는 n이 클수록 압도적이다.

f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 :\ f(n) \le c\, g(n) \ \text{ for all } n \ge n_0

먼저 보면 좋은 개념함수 극한 자연로그

알고리즘⁠(algorithm)⁠이 얼마나 빠른지는 컴퓨터와 언어, 프로그래머의 솜씨에 따라 달라집니다. 그런 것에 흔들리지 않게 비교하려고, 입력의 크기 n에 대한 걸음 수 $f(n)$ 을 세고 n이 커질 때 가장 빨리 자라는 부분만 남깁니다. 같은 크기의 입력이라도 걸음 수가 다를 수 있으니, 따로 말하지 않으면 크기가 n인 입력 가운데 가장 오래 걸리는 것(최악의 경우)을 셉니다. 상수배와 작은 항은 버립니다. $3n^2 + 20n + 50$ 걸음 걸리는 알고리즘은 그냥 $O(n^2)$ 이라고 씁니다.

이렇게 거칠게 봐도 되는 까닭은, n이 커지면 자라는 빠르기의 차이가 상수배 따위를 압도하기 때문입니다. $n =$ 을 키워 보세요. 세로축: .

log₂ n(청록), n(파랑), n log₂ n(보라), n²(노랑), 2ⁿ(분홍). 보통 눈금에서는 지금 n에서의 n²이 늘 보이도록 화면이 따라 물러납니다.

지금 걸음 수는 $\log_2 n \approx$ , $n \log_2 n \approx$ , $n^2 =$ , $2^n \approx$ 입니다. 1초에 10억 걸음을 가는 컴퓨터로 $n^2$ 걸음은 , $2^n$ 걸음은 걸립니다. 로그 $\log_2 n$ 은 n을 천 배로 늘려도 10쯤 늘 뿐이고, 지수함수⁠(exponential function)⁠ $2^n$ 은 n이 하나 늘 때마다 두 배가 되어 n = 100이면 이 컴퓨터로 약 40조 년, 우주 나이(약 138억 년)의 수천 배가 걸립니다. 그래서 걸음 수가 n의 다항식⁠(polynomial)⁠으로 묶이는 알고리즘을 '빠르다'고 부르고, 그런 알고리즘으로 풀리는 예/아니오 문제들의 모임을 P라고 합니다(P 대 NP 문제⁠(P versus NP problem)⁠).

정확한 뜻은 위의 식입니다. 어떤 상수 c와 문턱⁠(threshold)⁠ $n_0$ 이 있어서 그 뒤로는 f가 g의 c배를 넘지 않으면 $f = O(g)$ 입니다. 아래 그림에서 파란 곡선은 $f(n) = 3n^2 + 20n + 50$ , 노란 곡선은 $c \cdot g(n)$ 입니다. $g(n) =$ , $c =$ .

문턱 n₀(분홍 세로선)의 오른쪽에서는 노란 곡선이 언제나 파란 곡선 위에 있어야 합니다.

g가 $n^2$ 일 때 c가 3 이하이면 아무리 멀리 가도 안 되고, 3보다 조금만 크면 문턱이 아주 멀리 생깁니다. 결국 충분히 큰 n에서 $f/g$ 가 어떤 유한한 값 아래로 묶이느냐의 문제입니다. 그래서 극한⁠(limit)⁠ $\lim_{n\to\infty} f(n)/g(n)$ 이 유한한 값으로 있으면 $f = O(g)$ 입니다. 여기서는 그 극한이 3이니 c가 3보다 크기만 하면 됩니다(극한이 없어도 비가 묶여 있기만 하면 됩니다).

$O$ 는 위쪽 한계만 말합니다. 그래서 $3n^2 + 20n + 50$ 은 $O(n^3)$ 이기도 합니다. 참이지만 덜 알려 주는 말입니다. 흔히 'O(n²)이다'를 '정확히 n²만큼 자란다'로 읽지만, 그 뜻은 따로 $\Theta$ 가 맡습니다. 아래쪽 한계는 $\Omega$ (충분히 큰 n에서 늘 $f \ge c\,g$ 인 양수 c가 있다), 위아래가 모두 같은 차수이면 $\Theta$ 로 씁니다. 비교로 정렬하려면 최악의 경우 $\Omega(n \log n)$ 번 비교해야 한다는 비교 정렬의 하한⁠(comparison sorting lower bound)⁠이 $\Omega$ 의 대표적인 예입니다. O 표기는 1894년 독일의 수학자 파울 바흐만이 정수론⁠(number theory)⁠ 책에서 쓰고, 에드문트 란다우가 1909년 책에서 널리 퍼뜨렸습니다. 1976년 미국의 컴퓨터 과학자 크누스는 $\Omega$ 와 $\Theta$ 의 뜻을 지금처럼 정해 알고리즘 분석⁠(analysis of algorithms)⁠에 들여왔습니다.

이어지는 곳. 같은 말투가 수학 곳곳에 나옵니다. N 이하 소수⁠(prime number)⁠의 개수를 어림하는 소수 정리⁠(prime number theorem)⁠에서는 어림값과 참값의 차이(오차항)가 얼마나 빨리 자라는지를 O로 적습니다. 함수⁠(function)⁠가 충분히 매끄러우면 테일러 급수⁠(Taylor series)⁠를 n차에서 끊었을 때 남는 부분은 $O(x^{n+1})$ 인데, 여기서는 n이 커질 때가 아니라 x가 0에 다가갈 때 $x^{n+1}$ 의 상수배를 넘지 않는다는 뜻입니다. 스털링 공식⁠(Stirling's formula)⁠의 $\ln n! = n \ln n - n + O(\ln n)$ 도 같은 말투입니다. 알고리즘에서는 찾는 범위를 반씩 줄이는 이진 탐색⁠(binary search)⁠의 $O(\log n)$ , 좋은 정렬의 $O(n \log n)$ , 목록 크기와 상관없이 평균⁠(mean)⁠ 일정한 걸음에 찾는 해시 테이블⁠(hash table)⁠의 $O(1)$ 이 이 잣대로 비교됩니다. 조화급수⁠(harmonic series)⁠가 $\ln n + O(1)$ 이라는 사실은 퀵정렬⁠(quicksort)⁠의 평균 비교 횟수에서 다시 나옵니다.

이 개념이 나오는 긴 글

계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다. 조합론 세지 않고 세기 시의 운율을 세던 인도의 운율학자부터 오일러의 생성함수까지. 하나하나 늘어놓지 않고 경우의 수를 세는 법은 어떻게 자라났을까? 매칭과 흐름 짝을 찾는 알고리즘 의대 졸업생과 병원, 신장 기증자와 환자, 철도와 화물. 누구를 누구와 이을지 정하는 수학은 냉전의 철도 지도에서 노벨 경제학상까지 이어진다. 알고리즘과 복잡도 줄 세우기의 한계 카드 천 장을 가장 빨리 줄 세우는 방법은? 인구조사의 천공 카드에서 퀵정렬까지, 그리고 어떤 방법도 넘을 수 없는 n log n의 벽. 신경망과 기계 학습 배우는 기계 예를 보여 주면 규칙을 스스로 찾는 기계. 1958년의 퍼셉트론에서 오늘의 심층 신경망까지, 그 밑바닥에는 미분과 연쇄법칙이 있다. 언어 모델 다음 단어를 맞히는 기계 다음 낱말을 짐작하는 일만으로 어디까지 갈 수 있을까? 마르코프의 글자 세기에서 섀넌의 추측 게임, 트랜스포머와 규모의 법칙, 사람의 선호까지. 밑바닥에는 확률의 곱셈 규칙과 로그 하나가 있고, 그 수학은 모델이 왜 그럴듯하게 틀리는지도 말해 준다.

이 개념 위에 세워진 것

분할 정복 정렬 알고리즘

이 개념을 언급하는 페이지

소수 판정
… 곧 자릿수 k 가 늘 때 걸리는 시간이 고정된 지수 c 에 대해 k^c 의 상수배를 넘지 않는 방법입니다(점근 표기법). 그래도 실제로는 더 빠른 밀러–라빈이 쓰입니다. 합성수라는 것을 알아도 인수를 찾는 소인수분해는 …
중앙값
… 토니 호어가 내놓은 이 방법(퀵셀렉트)은 평균적으로 값의 개수 n에 비례하는 걸음( O(n) ,점근 표기법)이면 끝납니다. 값이 하나씩 들어올 때는, 가장 큰 값이나 가장 작은 값을 곧바로 꺼낼 수 있는 자료 …
가우스 소거법
… 미지수가 n 개면 소거에 드는 곱셈은 대략 n^3/3 번, 상수배를 무시하고 적으면 O(n^3) 입니다(점근 표기법). 행렬식을 정의대로 전개할 때의 n! 개 항과는 비교가 안 되게 적어서, 컴퓨터가 연립방정식을 풀 때도 …
편집 거리
… 따지면 금방 감당할 수 없지만, 표에는 칸이 (m+1)(n+1) 개뿐이라 계산량이 O(mn) 에 그칩니다(점근 표기법). 이웃 칸에서 값을 모아 오는 방식은 파스칼의 삼각형을 채우는 방식, 앞의 두 값을 기억해 두고 …
P 대 NP 문제
… 이나 n^3 걸음 안에 끝난다는 뜻입니다. 이런 성장 속도를 상수배를 무시하고 O(n^2) 처럼 적는 것이점근 표기법입니다. 걸음은 튜링 기계의 걸음으로 재지만, 어떤 합리적인 계산 모형을 써도 결론은 같습니다. 빠르게 …
역전파
… 계산해야 합니다. 가중치가 P개면 한 번 계산에 P에 비례하는 일이 드니 모두 합쳐 O(P^2) 입니다(점근 표기법). 역전파는 앞으로 한 번, 거꾸로 한 번이면 P개의 기울기를 모두 얻고, 거꾸로 계산의 비용도 앞으로 …
점화식
… 풀고, 두 답을 합치는 데 n걸음이 든다는 뜻입니다. 그 답이 n\log n 정도라는 것이 분할 정복과점근 표기법의 기본 계산입니다. 규칙이 일차식이 아니면 사정이 전혀 다릅니다. x_{n+1} = r …
생성함수
… 확률론에 생성함수를 체계적으로 썼습니다. 지금도 알고리즘의 평균 걸음 수를 세고 그 증가 속도(점근 표기법)를 어림할 때 생성함수가 기본 도구입니다. 프로그래밍에서 리스트나 나무 같은 타입의 값을 크기별로 세는 …
알고리즘
… 빼기만 쓰면 (n, 1) 에서 n걸음이 걸립니다. 입력이 커질 때 걸음 수가 어떻게 자라는지를 재는 말이점근 표기법이고, 두 방법의 차이는 자릿수만큼 자라느냐 수 자체만큼 자라느냐입니다. 무엇이 '명확한 절차'인지를 …
이진 탐색
… 이면 이진 탐색은 많아야 번, 순차 탐색은 최악의 경우 번 비교합니다. 로그와 그 역인 지수의 차이,점근 표기법으로 말하면 O(\log n) 과 O(n) 의 차이입니다. '같다'로 끝나는 마지막 한 번을 빼면, 비교 …
분할 정복
… 나오는 \Theta(g) ('세타 g')는 'n이 커질 때 상수배를 무시하면 g만큼 자란다'로 읽습니다.점근 표기법의 O가 위쪽 한계만 말한다면, Θ는 위아래를 함께 말합니다. 하위 문제 수 a = , 나누고 합치는 일 …
비교 정렬의 하한
… \log n) 입니다. 병합 정렬의 최악은 첫째 항 n \log_2 n 까지 이 하한과 같으니,점근적으로최선입니다. n = 이면 하한은 번, 병합 정렬의 최악은 번, n \log_2 n 은 입니다. 모든 순서가 …
해시 테이블
… 삽입할 수 있으니 그 비용을 나눠 내면 한 번에 상수만큼입니다. 그래서 평균 O(1) 이 유지됩니다(점근 표기법). 이 '나눠 내기' 평균은 확률과 상관없이 늘 성립하는 평균이라, 해시가 고르게 퍼진다는 가정에 기댄 …
최소 신장 트리
… 구조로 거의 즉시 알 수 있어서, 전체 시간은 변 m개를 정렬하는 O(m \log m) 이 좌우합니다(점근 표기법). 1957년 벨 연구소의 로버트 프림이 발표한 방법(체코의 수학자 보이테흐 야르니크가 1930년에 …
홀의 정리
… 보입니다. 사람마다 증가 경로를 한 번씩 찾으면 되니 전체 비용은 사람 수와 변 수의 곱 정도입니다(점근 표기법). 반면 홀 조건을 하나하나 확인하려면 사람들의 모든 부분집합, 곧 멱집합의 원소 2^n 개를 봐야 …
최대 흐름 최소 절단 정리
… 1인 최단 경로 찾기인 셈입니다. 이렇게 하면 늘리는 횟수가 꼭짓점 수와 변 수의 곱 정도로 묶입니다(점근 표기법). 증가 경로를 아무렇게나 고르면 늘리는 횟수가 용량의 크기에 따라 불어나고, 용량이 무리수이면 끝나지 …
안정 매칭
… 왜 늘 끝나고, 왜 안정할까요? 학생은 같은 학교에 두 번 지원하지 않으니 지원은 많아야 n^2 번입니다(점근 표기법). 학교는 한 번 누군가를 보류하면 끝까지 누군가를 보류하고 상대는 좋아지기만 합니다. 끝났는데 짝 없는 …
선형 계획법
… 들르게 만드는 문제를 만들어 최악의 경우 걸음 수가 변수의 수에 대해 지수적으로 늘 수 있음을 보였습니다(점근 표기법). 계산량이 변수의 수에 대한 다항식으로 묶이는 방법은 1979년 레오니트 하치얀의 타원체법(답을 품은 …
자동 미분
… × 행렬'(n×n이면 곱셈 약 n^2 번)로 끝나고, 행렬끼리의 곱(약 n^3 번)을 피할 수 있습니다(점근 표기법). 범주론을 아는 독자에게 연쇄 법칙 D(g \circ f)_x = Dg_{f(x)}\, Df_x (점 …
어텐션
… 서로를 모두 보므로 점수 표는 n×n이고, 계산량과 메모리가 길이의 제곱에 비례합니다( O(n^2 d) ,점근 표기법). 문맥을 길게 늘리기 어려운 주된 까닭입니다. 셀프 어텐션. 쿼리, 키, 값이 모두 같은 문장에서 …
타입 추론: 힌들리–밀너
… ML 식에 타입이 있는지 판정하는 문제가 지수 시간 완전(DEXPTIME-완전)임을 보였습니다(이런 문제는점근 표기로 쓴 어떤 다항식 시간 안에도 풀 수 없음이 증명되어 있습니다). 또 ML과 Haskell은 let …
모노이드
… 단계 수입니다. n개라면 n − 1단계 대 \lceil\log_2 n\rceil 단계입니다(분할 정복,점근 표기법). 수백만 개의 수를 더할 때 여러 기계가 조각을 나눠 더한 뒤 그 결과를 다시 더해도 되는 것은 덧셈이 …
이산 푸리에 변환과 고속 푸리에 변환
… 반으로 나누어 풀고 합치는 이런 방법이 분할 정복이고, 계산량을 이렇게 N의 함수로 어림하는 말이점근 표기법입니다. N이 2의 거듭제곱이 아니어도 N을 인수들로 쪼개는 비슷한 방법이 있습니다. 이 쪼개기는 두 번 …

이 페이지가 가리키는 개념

알고리즘 지수함수 eˣ P 대 NP 문제 비교 정렬의 하한 도널드 크누스 소수 정리 테일러 급수 스털링 공식 이진 탐색 정렬 알고리즘 해시 테이블 조화급수