Big - O 표기법

출처 : http://blog.naver.com/anjindago?Redirect=Log&logNo=150119261447

 

빅오 표기법이란?

어떤 하나의 함수의 복잡도를 정의하는 데 즐겨 사용하는 것.
간단히 말하자면 알고리즘이 처리할 자료집합의 크기가 성장함에 따라 알고리즘의 효율이
어떻게 변화하는지를 대략적이나마 추정하는 하나의 함수라고 정의 할 수 있다.


알고리즘의 복잡도를 표현하는 데 흔히 쓰이는 함수들이 몇 가지 있는데,
복잡도의 낮은 것부터 높은 순으로 나열해보자면
(상수), (log₂n), (n), (nlog₂n), n², n³, 2ⁿ 이라고 한다.


O(c)
빅 O 표기에서 c는 상수를 뜻한다.
상수 함수의 그래프는 항상 수평을 유지한다. 이는 알고리즘의 수행에 걸리는 시간이 자료집합의 크기에
상관없이 항상 동일하다는 뜻이다. 대체로 이런 함수들이 가장 빠른 것으로 간주된다.


O(log₂n)
로그 기반의 알고리즘은 자료의 크기에 의존적인 알고리즘들 중에서는 가장 효율적인 것으로 간주된다.
즉, 데이터가 추가되면 될수록 효율이 좋아지는 녀석이다.


O(n)
선형 함수라 불리며, 어떠한 알고리즘이 1000개의 항목을 20초안에 처리한다면, 2000개의 항목은
40초에 처리하게되는 자료의 크기와 직접적인 관계를 갖는 함수이다.


O(nlog₂n)
이 함수는 일반적인 정렬 알고리즘이 가져야 할 최소한의 복잡도로 간주된다.


O(n²)
자료가 증가함에 따라 급격히 커지기 때문에 대부분의 과제들에 비해 비효율적이라고 간주된다.
예를들어 1000개의 항목을 처리하는데 20초가 걸렸다면 2000개의 항목을 처리하기위해선 80초의
시간이 소요된다. 항목의 갯수가 2배증가하면 시간은 4배가 증가하는 셈이다.
일반적으로 어떤 알고리즘이 O(n²)이라면 일단 다른 알고리즘을 찾아보는 것이 더 낫다. (최대한 쓰지말자)
전형적인 예는  for 루프 안에 다른 for 루프가 내포된 형태이다.


O(n³)
1000개의 항목을 처리하는데 20초라면 2000개는 160초(8배)
위의 것보다 더 최악... 그냥 쓰지말자


O(2ⁿ )
흔히 기수 2 지수 함수라 부르며 항목 개수가 1 증가할 때마다 함수는 2배가 된다.
매우 비효율적이므로 피해야하는 알고리즘이다.


여러가지 복잡도들의 비교

복잡도	16개	32개	64개	128개
O(log n)	4초	5초	6초	7초
O(n)	16초	32초	64초	128초
O(nLog n)	64초	160초	384초	896초
O(n2)	256초	17분	68분	273분
O(n3)	68분	546분	74시간	24일
O(2n)	18시간	136년	5억년	--------