점근 표기와 성장률

충분히 큰 범위의 상한은 양화된 주장이다

점근 표기는 충분히 큰 입력에서 함수가 자라는 방식을 설명합니다. 정확한 실행 시간이 아니고 기호만으로 최선·평균·최악 경우도 정해지지 않습니다. 비용 함수와 계산·표집 모형을 먼저 정의하세요.

충분히 큰 곳에서 f≥0,g>0일 때 f∈O(g)는 어떤 C>0,n₀가 존재하여 모든 n≥n₀에서 f(n)≤Cg(n)이라는 뜻입니다. 유한 크기의 표본만으로 전체 꼬리 범위를 입증하지는 못합니다.

상수와 시작점은 증인이다

실험은 작은 양의 정수 a와 음이 아닌 정수 b의 f(n)=an+b를 사용합니다. C>a이면

라 정수 시작점은 max(1,ceil(b/(C−a)))입니다. f=2n+3,C=3이면 n₀=3이 됩니다. n₀=1은 5>3이라 실패합니다. 특정 증인 쌍의 실패이지 O(n) 소속의 실패가 아닙니다.

C=2,b=3이면 2+3/n>2라 유한 시작점이 없습니다. 그래도 C=3은 유효합니다. 증명서 하나의 실패를 불가능으로 읽으면 양화사가 바뀝니다.

Big-O는 정확한 등식이 아니다

n≥1에서 2n≤2n+3≤5n이라 Θ(n)입니다. 같은 비교 함수의 상수배 위·아래에 놓입니다. Ω는 이 규약에서 충분히 큰 범위의 하한입니다.

n≤n²이므로 같은 함수는 O(n²)이기도 합니다. 참인 상한이 가장 날카로운 설명인 것은 아닙니다. f=O(g)는 관례적으로 쓰는 함수류 소속 표기이지 보통 함수 하나와의 등식이 아닙니다.

상한의 부정은

입니다. n²과 n에서는 C,n₀보다 큰 정수 n을 고르면 n²>Cn입니다. 큰 비율 몇 개를 본 것이 아니라 O(n)이 아님을 증명합니다.

성장 함수 비교

로그 성장률 비교에서는 1보다 큰 고정 밑을 사용합니다. 그 사이의 변경은 양의 상수배여서 점근류를 바꾸지 않습니다. 다항식 차수와 지수는 더 다릅니다. n=8에서는 n²=64,2ⁿ=256이고 n=16에서는 256과 65,536입니다. 차이를 보여주는 예이지 그 자체가 무한 범위 정리는 아닙니다.

엄밀한 비교에는 비율·상한·뒤의 해석학 극한 같은 논증이 필요합니다. 유한 log-log 기울기 적합을 보편 복잡도 정리로 바꾸지 마세요.

작은 o는 더 강합니다. 양의 비교 함수에서 비율이 0으로 가야 합니다. 0이 아닌 n의 상수배는 O(n)이지만 o(n)은 아닙니다. 문헌의 규약을 확인하세요.

비율 그림 읽기

파랑은 n=1,…,128의 f(n)/n, 주황은 C입니다. n₀의 보장은 그린 구간이 아니라 분석적 식으로 검사합니다. 임의의 모르는 함수라면 유한 구간이 C 아래라는 사실만으로 이후 전체를 보장할 수 없습니다.

이 명시적 일차 모형은 대수식이 일반 결과를 줍니다. 경계 비교를 정확히 보여주려고 정수 상수를 조작합니다. 실제 컴퓨터를 측정한 시간이 아니라 합성 비용입니다.

AI 시스템과 연구 비교

무엇이 커지는지 밝혀야 합니다. 표본·토큰·차원·매개변수·탐색 깊이는 다른 변수입니다. 메모리·통신·산술 비용도 다를 수 있고 유한 크기에서는 상수가 지배할 수 있습니다.

구현 가정·희소성·정밀도를 적으세요. 실행 시간은 지정 환경의 경험 주장, 점근 상한은 계산 모형의 수학 주장입니다. 어느 쪽도 에너지나 예측 성능 개선을 자동으로 뜻하지 않습니다.

연습과 근거

1. f=3n+4,C=5의 시작점은? 답: n₀=2입니다.
2. n도 O(n²)인가요? 답: n≥1에서 참이지만 느슨합니다.
3. Big-O를 반박하는 양화사를 적으세요.
4. AI 연산의 크기 변수를 정하고 이론 횟수와 실제 시간을 구분하세요.

배경은 MIT Mathematics for Computer Science를 참고하세요. 선형 증명서와 양화 논증은 직접 유도했습니다.