2012년 11월 11일 일요일

Big O법

다른말로 럼바우의 점근 표기법, 쉽게말해 특정 알고리즘의 계산량을 수학적으로 다루기 위한 계산이론.

흔히 O(n)으로 나타내며, n=1000이라면 어떠한 연산을 수행함에 있어 1000번 이내에는 해당 작업을 마칠수 있다는 식의 표기. (결국 모든 처리에 있어 Worst case상의 계산)


일반적으로 사용되는 오더는 다음과 같다. (는 일본 위키의 럼바우의 기호 페이지를 참조)


O(1) : 정수함수(Constant) : 정수의 홀수판별 
O(log*n) : 반복대수(iterated logarithmic) : Hopcroft, Ullman에 의한 소집합 데이터 구조에 관련된 탐색 알고리즘
O(log n) : 대수(logarithmic) : 정렬이 완료된 배열의 바이너리 검색
O((log n)^c) : 대수다항식(polylogarithmic) AKS소수판별법에 의한 자연수 n의 소수판정(n은 입력사이즈는 아님)
O(n^c),0<c<1 : 분수지수함수(Fractional power) : kd-tree상의 탐색 
O(n) : 선형함수(linear) : 비 정렬 배열상의 탐색(분산 웨이브렛 변환:DWT) 
O(n log n) : 표선형, 선형대수(Linearithmic, Loglinear, or quasilinear) : 히프소트, 고속 푸리에 변환 
O(n^2) : 2승함수 : 삽입 소트, 분산 푸리에 변환 
O(n^c),c>1 : 다항식함수(Polynomial) :플로이드 와셜 알고리즘 
O(c^n) = 2^(O(n)) : 지수함수(Exponential) : (현재 가장 빠른) 외판원 문제의 해법 
O(n!) : 팩토리얼(Factorial) : 두 논리식이 같은지의 판정, 외판원 문제등의 'NP완전'문제의 전검색에 의한 해법. 
O(2^c^n) : 이중 지수 함수(double exponential) : AC단일화자의 완전집합의 탐색

각 소트 알고리즘 별의 복잡도는 아래 페이지를 참조.
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

STL의 std::sort의 경우 quick sort를, std::stable_sort의 경우는 merge sort로 구현하고 있음.
속도면은 대개의 경우 n log n으로 별 차이가 없어보이나, 메모리 사용량이 Merge sort의 경우 worst에 한해 quick은 log n인데 반해 merge는 n인듯.

위 페이지의 표의 stable항목은 소트의 결과값이 최대한 기존의 우선순위를 유지해주는가 하는 여부. (같은 값에 한한 이야기)

참조 / References
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96

http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7