정의
컴퓨터 공학에서 Big-O 표기법은 알고리즘의 분류에 사용되는데, 입력의 크기가 변함에 따라 어떻게 반응하는지 나타낸다. 즉 입력에 따른 시간 복잡도 ( time complexity )를 나타낸다.
만약 알고리즘 A가 입력 N개에 대해서 (10N + 5) 연산 횟수를 가진다면, N 이 10이하의 작은 수라면, N에 곱해진 10이나, 더해진 5가 성능에 큰 영향을 주겠지만, N이 1010000 정도 되는 큰 수라면 10을 곱하거나, 5를 더하는 정도는 연산 시간에 큰 영향을 주지 못한다.
따라서 알고리즘 A를 Big-O 로 표기하면 O(N) 이된다. 마찬가지로, 알고리즘 B가 입력 N개에 대해 (10N2 + 88N + 38135)의 연산 한다고 가정하면 N 이 무한에 가깝게 클 수록 기울기를 정하는 요인은 N2 이 되므로 Big-O로 표기하면 O(N2 )이 된다.
따라서 알고리즘 A를 Big-O 로 표기하면 O(N) 이된다. 마찬가지로, 알고리즘 B가 입력 N개에 대해 (10N2 + 88N + 38135)의 연산 한다고 가정하면 N 이 무한에 가깝게 클 수록 기울기를 정하는 요인은 N2 이 되므로 Big-O로 표기하면 O(N2 )이 된다.
클래스
아래는 알고리즘을 분석할 때 사용하는 일반적인 분류들이다.
성능은 위에서 아래로 갈 수록 안좋다.
O(1) - constant - 입력 개수에 상관없이 같은 시간이 걸린다. 예를 들면 배열에 인덱스로 접근.
O(logN) - logarithmic - 대략적으로 입력이 10배 증가할 때 소요 시간이 1정도 증가한다. 대표적인 예는 이진검색( binary search )
O(N) - linear - 입력 개수에 대해 선형적으로 증가. 즉 10개 입력시 1의 시간이 소요되면, 100개 입력 시 10의 시간이 소요. 일반적으로 for 루프를 이용해서 탐색을 하는 경우에 해당된다.
O(N logN) - superlinear - O(N) 보다는 소요시간 증가폭이 크지만, 충분히 유용한 알고리즘. 성능좋은 정렬(Sort) 알고리즘 들이 이 범주에 속한다. (MergeSort, QuickSort...)
성능은 위에서 아래로 갈 수록 안좋다.
O(1) - constant - 입력 개수에 상관없이 같은 시간이 걸린다. 예를 들면 배열에 인덱스로 접근.
O(logN) - logarithmic - 대략적으로 입력이 10배 증가할 때 소요 시간이 1정도 증가한다. 대표적인 예는 이진검색( binary search )
O(N) - linear - 입력 개수에 대해 선형적으로 증가. 즉 10개 입력시 1의 시간이 소요되면, 100개 입력 시 10의 시간이 소요. 일반적으로 for 루프를 이용해서 탐색을 하는 경우에 해당된다.
O(N logN) - superlinear - O(N) 보다는 소요시간 증가폭이 크지만, 충분히 유용한 알고리즘. 성능좋은 정렬(Sort) 알고리즘 들이 이 범주에 속한다. (MergeSort, QuickSort...)
O(N2) - quadratic - 입력 개수 제곱에 비례해서 증가. 대표적인 예는 BubbleSort. 프로그래밍시 for루프를 2개 중첩해서 사용한 경우.
O(NC) - polynomial - 문자 그대로 N이 증가함에 따라 특정 계수로 증가하는 경우.
O(CN) - exponential - 매우 빠르게 증가. 위의 O(NC)보다 증가폭이 더 크다.
O(N!) - factorial - 최악의 성능, N이 작은 경우에도 증가폭이 기하급수적으로 늘어난다.
계산법
일반적인 계산이 가능한 경우.
O(1), O(N), O(N2) 등은 일반적으로 계산이 가능하다.
- O(1) 은 입력의 크기에 관계없이 일정한 시간이 소요되는 알고리즘으로, 배열의 인덱스로의 접근은 배열의 크기에 상관없이 같은 시간이 소요된다.
- O(N) 은 정렬되지 않은 배열에서의 특정값 검색처럼 모든 원소를 순회해야 하는 경우이다
int getValue( int index )
{
return array_[index];
}
- O(N) 은 정렬되지 않은 배열에서의 특정값 검색처럼 모든 원소를 순회해야 하는 경우이다
int findValue( int value )
{
for( int i = 0; i < ARRAY_MAX; ++i )
{
if( array_[i] == value )
return array_[i];
}
return 0;
}
위 함수는 평균적으로 1/2N, 최악의 경우 N 이지만, big O 로 표기하면 상수는 무시되므로O(N) 이 된다.
- O(N2) 은 for문을 중첩해서 사용하는 경우에 해당되며 대표적으로 BubbleSort가 있다.
void BubbleSort( int array[], int arraySize )
{
for( int i = 0; i < arraySize; ++i )
{
for( int j = 0; j < arraySize - 1; ++j )
{
if( array[j] > array[j+1] )
{
// swap
int tmp = array[j+1];
array[j+1] = array[j];
array[j] = tmp;
}
}
}
}
일반적이지 않은 경우는?
- O(logN) 과 O(N logN) 은 위에서 본 경우처럼 명확하게 계산하기 힘들다. 이해를 돕기 위해 실제 수치로 계산을 해보자.
N = 10 : log10 = 1 10log10 = 10
N = 20 : log20 = 1.3 20log20 = 26.02
N = 100 : log100 = 2 100log100 = 200
N = 1000 : log1000 = 3 1000log1000 = 3000
분명히 O(N logN)은 O(N) 보다는 그래프로 그렸을 때 기울기가 가파르다. 하지만 정렬알고리즘의 경우 O(N logN) 보다 뛰어날 수 없다는게 수학적으로 증명되었으니, 복잡도가 O(N logN)이라면 좋은 알고리즘에 속한다.
N = 20 : log20 = 1.3 20log20 = 26.02
N = 100 : log100 = 2 100log100 = 200
N = 1000 : log1000 = 3 1000log1000 = 3000
분명히 O(N logN)은 O(N) 보다는 그래프로 그렸을 때 기울기가 가파르다. 하지만 정렬알고리즘의 경우 O(N logN) 보다 뛰어날 수 없다는게 수학적으로 증명되었으니, 복잡도가 O(N logN)이라면 좋은 알고리즘에 속한다.
전화번호부 문제
O(logN) 복잡도를 설명하는 문제 중 전화번호부 문제가 있다.
일반 전화번호부와 다르게 알파벳에 따른 인덱스가 없는 전화번호부에서 "John Smith"를 찾는다고 가정해보자. 일단 전화번호부의 가온데를 펴고 Smith의 "S"를 찾는다. 처음 연 페이지에 John Smith가 있을 수 있지만, 대부분의 경우 없을것이다. 그럼 그 페이지의 알파벳을 보고 다음 펼칠곳을 찾는다. 만약 펼친 페이지가 "I" 라면 S는 뒤에 있으니 그 뒤에서 똑같이 중간을 펼치고 알파벳을 비교 한다.
위 내용이 바로 이진검색 ( binary search ) 이다. 페이지가 1,000,000 페이지라면 최대 20번만 페이지를 찾는 다면 반드시 원하는 페이지를 찾을 수 있다.( 220 = 1048576 )
Big-O로 표현하면 O(logN)이 된다. logarithmic complexity 에서 로그의 밑은 중요하지 않다. ln이든, log2N, log10N 이든, Big-O로 표현하면 모두 logN이 된다.
반대로, 전화번호를 가지고 이름을 찾는다고 가정해 보자. 전화번호부는 이름으로 정렬된 데이터이기 때문에 일치하는 전화번호를 찾기 위해서는 처음부터 마지막까지 모든 번호를 비교해서 검색해야 한다. 페이지가 1,000,000 페이지 전화번호부라면 1번에 전화번호가 있을 확률도 있지만 1,000,000번째 전화번호가 있을 확률도 같다. 확률로 나타내면 1/2N이 되겠지만, Big-O로 표현하면 O(1/2N) 은 O(N)이 되므로, 복잡도는 O(N)이 된다.
일반 전화번호부와 다르게 알파벳에 따른 인덱스가 없는 전화번호부에서 "John Smith"를 찾는다고 가정해보자. 일단 전화번호부의 가온데를 펴고 Smith의 "S"를 찾는다. 처음 연 페이지에 John Smith가 있을 수 있지만, 대부분의 경우 없을것이다. 그럼 그 페이지의 알파벳을 보고 다음 펼칠곳을 찾는다. 만약 펼친 페이지가 "I" 라면 S는 뒤에 있으니 그 뒤에서 똑같이 중간을 펼치고 알파벳을 비교 한다.
위 내용이 바로 이진검색 ( binary search ) 이다. 페이지가 1,000,000 페이지라면 최대 20번만 페이지를 찾는 다면 반드시 원하는 페이지를 찾을 수 있다.( 220 = 1048576 )
Big-O로 표현하면 O(logN)이 된다. logarithmic complexity 에서 로그의 밑은 중요하지 않다. ln이든, log2N, log10N 이든, Big-O로 표현하면 모두 logN이 된다.
반대로, 전화번호를 가지고 이름을 찾는다고 가정해 보자. 전화번호부는 이름으로 정렬된 데이터이기 때문에 일치하는 전화번호를 찾기 위해서는 처음부터 마지막까지 모든 번호를 비교해서 검색해야 한다. 페이지가 1,000,000 페이지 전화번호부라면 1번에 전화번호가 있을 확률도 있지만 1,000,000번째 전화번호가 있을 확률도 같다. 확률로 나타내면 1/2N이 되겠지만, Big-O로 표현하면 O(1/2N) 은 O(N)이 되므로, 복잡도는 O(N)이 된다.
댓글 없음:
댓글 쓰기