점근 표기법

덤프버전 :

'''해석학 · 미적분학
Analysis · Calculus'''

[ 펼치기 · 접기 ]
기본 이론
함수
합성 · 항등원 · 역원 · 멱함수( 비례·반비례 ) · 초등함수( 대수함수 · 초월함수) · 특수함수 · 범함수 · 다변수 ( 동차 · 숨은 함수( 다가 함수 )) · 그래프 · 대칭 · 증감표 · 극값 · 연속 · 매끄러움 · 계단형 · 미끄럼틀형 · 볼록/오목 · 닮은꼴 함수 · 병리적 함수
극한
부정형 · 유계( 콤팩트성 ) · 어림 · 근방 · 수열의 극한 · 엡실론-델타 논법 · 수렴 ( 균등수렴 ) · 발산 · 점근선 · 무한대 · 무한소 · 스털링 근사 · FEM
수열
규칙과 대응 · 단조 수렴 정리 · 급수(멱급수) · 테일러 급수 ( 일람 ) · 조화급수 · 그란디 급수 · 망원급수 ( 부분분수분해 ) · 오일러 수열 · 베르누이 수열 · 파울하버의 공식 · 리만 재배열 정리
미분
도함수 일람 · 차분 · 유율법 · 변화량 · 변분법 · 도함수 ( 편도함수 ) · 곱미분 · 몫미분 · 연쇄 법칙 · 역함수 정리 · 임계점 ( 변곡점 · 안장점 ) · 미분형식 · 미분방정식 ( 풀이 ) · [math(\boldsymbol\nabla)] · 라그랑주 승수법
적분
역도함수 일람 · 부분적분 ( LIATE 법칙 · 도표적분법 · 예제 ) · 치환적분 · 정적분 ( 예제 ) · 이상적분 · 중적분 ( 선적분 · 면적분 ) · 르베그 적분 · 스틸체스 적분 · 코시 주요값
정리 · 토픽
중간값 정리 · 최대·최소 정리 · 평균값 정리 ( 롤의 정리 ) · 로피탈의 정리 · 미적분의 기본정리 · 스토크스 정리 ( 발산 정리 ) · 중심극한정리 · 오일러 공식 ( 드 무아브르 공식 ) · 오일러 동차함수 정리 · 리우빌의 정리 · 부동점 정리 · 뉴턴-랩슨 방법 · 리시 방법 · 좌표계 · 소수 정리 · 라플라스 변환 · 푸리에 해석 ( 푸리에 변환·이산 푸리에 변환) · 아다마르 변환 · 바젤 문제 · 라마누잔합 · 바이어슈트라스 분해 정리 · 미타그레플레르 정리 · 디랙 델타 함수 · 2학년의 꿈 · 0.999…=1 · 리만 가설미해결 · 카오스 이론미해결
분야
실해석학 · 복소해석학 · 수치해석학 · 측도론 · 미분기하학 · 해석기하학 · 해석적 정수론 · 확률론 · 수리물리학 · 수리경제학(경제수학) · 공업수학



'''이론 컴퓨터 과학
{{{#fff

Theoretical Computer Science
'''

[ 펼치기 · 접기 ]
이론
기본 대상
수학기초론(수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론) · 이산수학(그래프 이론) · 수치해석학 · 확률론통계학] · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론
재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론
FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
계산 복잡도 이론
점근 표기법 · 튜링 기계^고전, PRAM, 양자, 비결정론적^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법)
수학적 최적화
조합 최적화
외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화
내부점 방법 · 경사하강법
선형계획법
심플렉스법
정보이론
데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
컴퓨팅 방법론
병렬 컴퓨팅(병렬 아키텍처 · 암달의 법칙 · 병렬 알고리즘) · 분산 컴퓨팅(분산 알고리즘 · 클러스터 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅) · 멀티코어 컴퓨팅 · 대칭형 다중 처리(SMP)
암호학
해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식
블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식
공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
프로그래밍 언어이론
프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초
정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현
배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^, 피보나치 힙^
계산 수론 및 암호학
밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘
계산기하학
볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론
탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학




1. 개요 및 정의
1.1. 연관된 표기법
2. 해석학에서의 활용법
3. 컴퓨터 과학에서의 점근 표기법
4. 참고
5. 관련 문서



1. 개요 및 정의[편집]


/ asymptotic notation
수리과학의 여러 분야에서 함수의 증감 추세를 비교하는 표기법이다. 란다우 표기법(Landau notation)이라 부르기도 한다. [1]

점근 표기법(asymptotic notation)

실함수 [math(f,\,g: [0,\,\infty) \rightarrow \mathbb{R})]에 대해

1. 상수 [math(M>0,\,c>0)]가 존재하여 [math(x>M \Rightarrow |f(x)| \le c g(x) )]를 만족시킬 때, 이를 "[math(x \rightarrow \infty)]에 대해 [math(f(x) = O(g(x)) )]"라 표기한다.

1. 상수 [math(\epsilon>0,\,c>0)]가 존재하여 [math(|x-a|<\epsilon \Rightarrow |f(x)| \le c g(x) )]를 만족시킬 때, 이를 "[math(x \rightarrow a)]에 대해 [math(f(x) = O(g(x)) )]"라 표기한다.

무한대 점근의 정의는 실수열 [math(f,g : \mathbb{N} \rightarrow \mathbb{R})]에 대해서도 동일하게 정의될 수 있고, 이 편이 훨씬 많이 쓰인다.

수식 입력 편의상 이탤릭체를 사용하는 경우가 대부분이나, 흘림체인 [math(\mathcal{O})]를 사용하는 경우도 많이 있다. 다만, [math(O)]를 처음 사용한 바흐만, 란다우의 서적이나 이를 컴퓨터 과학에 본격적으로 들여온 도널드 커누스의 노트도 딱히 글꼴을 지정하진 않았다.


1.1. 연관된 표기법[편집]


커누스는 란다우의 표기법을 종합해 다음의 4가지 표기법을 같이 정리하였다.
  • [math(f(x) = o(g(x)) )]: 임의의 [math(c>0)]에 대해 [math(M)]이 존재하여 [math(x>M \Rightarrow |f(x)| \le c g(x) )]
  • [math(f(x) = \Omega(g(x)) )]: [math(M,c>0)]이 존재하여 [math(x>M \Rightarrow |f(x)| > c g(x) )]
  • [math(f(x) = \omega(g(x)) )]: 임의의 [math(c>0)]에 대해 [math(M)]이 존재하여 [math(x>M \Rightarrow |f(x)| > c g(x) )]
  • [math(f(x) = \Theta(g(x)) )]: [math(f(x)>0)] 중에서 [math(f(x)=O(g(x)) )]이며 [math(f(x)=\Omega(g(x)) )]
극미한 접근([math(x \rightarrow a)])의 경우도 비슷하게 정의할 수 있다.

이외에도 점근을 나타내는 다음의 다양한 표기가 있다.
  • 표기 [math(f \ll g)]는 [math(f=O(g) )]와 동치이다.
  • 표기 [math(f \asymp g)]는 [math(f = \Theta(g) )]와 동치이다.
  • 표기 [math(f \sim g)]는 [math(\lim_{x\to\infty}\limits (f/g)=1)]과 동치이다.


2. 해석학에서의 활용법[편집]


극한과 비슷하게 생각할 수 있지만 세부적인 성질은 달라지는 것들이 많다. 예를 들어서

[math(\lim_{x\to\infty}\limits \left|\dfrac fg\right| < \infty \Rightarrow f = O(g) )]
[1] 이 표기법을 처음 사용한 것은 파울 바흐만이었으나, 실제로 이 표기법이 수학계에서 대중화된 것은 란다우가 자신의 책에서 지속적으로 이 표기법을 사용하였기 때문에 란다우 표기법이라는 별칭으로도 불린다.

이 명제의 은 성립하지 않는데, [math((f,\,g) = (\sin(x),\,1) )] 같은 예시처럼 극한이 진동할 수도 있기 때문이다. 다만, 다음은 성립한다.

[math(\displaystyle f =O(g) \Leftrightarrow \limsup \left| \frac{f}{g} \right| < \infty )]

[math(\displaystyle )]
해석학에서의 점근 표기법은 단순히 [math(f=O(g))]꼴뿐만 아니라 굉장히 자유롭게 쓰이는데, 예를 들어서

[math(\displaystyle \sum_{i=1}^N \frac1i = \log N + \gamma + O(N^{-1}) )] ([math(N \rightarrow \infty)]일 때)

혹은

[math(e^x = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots + \dfrac{x^k}{k!} + O(x^{k+1}) )] ([math(k)]는 고정된 자연수이고 [math(x \rightarrow 0)]일 때)

와 같은 표기법은 좌우변의 차이인 오차항이 O-표기법을 따르는 함수라는 것을 의미한다. 이런 표기법이 빈번하게 쓰이는 이유 중 하나는 O-표기법이 사칙연산에 비해 비교적 잘 행동하기 때문이다. 예를 들어서 [math(f_1 = O(g_1))], [math(f_2=O(g_2))]이면 [math(f_1 + g_1 = O(g_1+g_2))], [math(f_1 f_2 = O(g_1 g_2))] 등이 성립한다. 다만, 사칙연산에 대해서만 성립할 뿐이고, [math(e^f = O(e^g))] 등이 성립하지는 않는다. 이런 경우에는 [math(f=e^{O(x)})] 같은 표현이 쓰이는데, 이는 [math(g=O(x))]인 함수 [math(g)]가 존재해서 [math(f = e^g)]가 된다는 것을 의미한다.

O-표기법은 다변수함수, 벡터함수, 복소함수 등에서 쓰이기도 한다. 예를 들어서, 다변수 테일러 정리의 표현식을 다음처럼 쓸 수 있다.

[math(\displaystyle f(x+h) = \sum_{|\alpha| \le m} \frac{\partial^{\alpha} f(x)}{\alpha_1! \cdots \alpha_n!}h^{\alpha} + O(\|h\|^{m+1}) )]



3. 컴퓨터 과학에서의 점근 표기법[편집]


일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다. Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간복잡도를 가진다는 의미이다. 물론 공간복잡도에 대해서도 사용될 수 있다. 사실 공간복잡도의 이론적인 상한은 시간복잡도이기 때문에 [2] 시간복잡도가 공간복잡도보다 조금 더 중요하게 취급받는다.

사실 현업에서는 알고리즘이 2배, 3배, 상수배 빨라지는 것도 의미가 있고, 당연히 계산 Step의 개수를 정확히 센 결과가 Asymptotic보다 더 정확한 지식이다.

하지만 이걸 쓰는 이유는 [math(n)]이 커지면 커질수록 언젠가는 Big-O 복잡도가 큰 알고리즘이 Big-O 복잡도가 작은 알고리즘을 역전한다는 수학적인 사실이 있기 때문에 생기는 원론적인 구분이 가능하다는 것이다.

예를 들면 극단적으로 [math(9999n)]개의 step이 필요한 알고리즘이 [math(0.001n^2)] 보다 느려 보이더라도 [math(n)]이 커질 때 언젠가는 [math(0.001n^2)]의 알고리즘이 역전한다는 것이다. 이건 다항 알고리즘과 지수 알고리즘의 차이에서도 존재하고 [math(2^{0.001n})]처럼 아무리 상수항이 작은 지수 알고리즘이라도 언젠가는 [math(n^{9999})]보다 느려지는 시점이 올 수밖에 없다.
이 때문에 수많은 수학자들이 최대한 선형 알고리즘을 찾거나 그게 아니더라도 다항 알고리즘을 찾으려고 고생하는 이유이기도 하고, P-NP 문제가 중요한 이유이기도 하다.

Big-O 계산의 예시로는 [math(O(5n+7)=O(5n)=O(n))]이 되고, [math(O(n^2+25)=O(n^2))]을 들 수 있다. 여기서 등호 기호([math(=)])를 '같다(equals)'는 뜻이 아니라 '~이다(is)', '~쯤 된다(approx)'라고 해석하면 기호의 혼란을 피할 수 있다. 경우에 따라 [math(O(g(n)) )]을 하나의 집합으로 보고 [math(f(n) \in O(g(n)) )]으로 표기하기도 하는데, 과거보다 현대로 올수록 많은 알고리즘, 미적분학, 해석학 교과서들이 이 집합 개념을 사용하고 있다. 보다 수학적으로 엄밀해지고, asymptotic tight bound를 정확히 특정하는 Big-θ 표기법에서는 [math(\theta(g(n)) )]을 간단히 [math(O(g(n))\cap\Omega(g(n)) )]으로 정의할 수 있다. [math(f(n)=O(g(n)) )]에서 등호는 [math(\in)]의 의미를 imply하며 동시에 직관성을 얻는다. 이 '같다'의 직관성은 Big-O notation의 오용을 초래[3]했고, Big-Theta notation을 탄생하게 한 배경이 되었다.

파일:2-4-1.png

간단한 예를 한번 들어보자. 디스크에 있는 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자. 그림에서 파일 크기가 작다면, 즉 [math(n)]이 작다면 [math(O(n))]의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다(비용은 고려하지 않는다면).[4] 파일이 아무리 커도, 즉 [math(n)]이 아무리 커도 비행기를 통한 파일 전송은 [math(O(1))]로 항상 일정한 시간이 소요되기 때문이다. 이것이 바로 점근적 실행 시간이며, 빅오는 점근적 실행 시간을 표기하는 방법 중 하나다.

4. 참고[편집]




5. 관련 문서[편집]




파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-16 06:16:37에 나무위키 점근 표기법 문서에서 가져왔습니다.

[2] 메모리를 할당하는 것도 일종의 명령어이기 때문에 컴퓨터는 시간을 초월한 넓이의 공간을 접근하지 못한다. 튜링 머신에서 테이프를 옮기는 동작과 연산을 하는 동작 사이에 원론적이 구분이 없다는 점을 들어 이해할 수 있다. [3] 선형대수학에서 생성기저에 대해 다루는 경우에도 이와 같은 등호 기호의 오남용을 볼 수 있다. [4] 실제로 구글 및 NASA 등 PB 단위로 데이터를 취급하는 단체, 업체들이 이렇게 데이터를 항공 운반하는 경우가 자주 있다.