빅오(Big-O) 표기법

> Big-O 표현방법은 알고리즘의 퍼포먼스를 이야기할때 상당히 좋은 방법이다.

▶ O(1)

void printFirstItem( int[ ] array )

{

cout << array[0] << endl;

}

1개의 배열을 받아 단순히 1개의 인덱스에만 접근한다면 O(1)이 된다. 

[ 예시 ]

stack에 push, pop을 할때나 Hash Table을 이용해 접근할 때에도 O(1)이 된다. 

1개의 키에만 접근하면 100만개의 item이 있더라도 1번의 접근이기 때문에. 

** nO(1) = O(1)이된다. 앞의 인자n은 상관하지 않는다. 

void printFirstItem( int[] array )

{

cout << array[0] << endl;

cout << array[1] << endl;

}

이렇게 되면 2 * O(1) 이 되지만, 앞의 2는 알고리즘의 퍼포먼스에 큰 영향을 끼치지 않는다. 그러므로 상수는 항상 무시하게 된다.

▶ O(log n)

[ 예시 ]

2진 트리의 시간복잡도

1을 삽입한다고 할 때, 2진트리에서 8개의 아이템이 있는경우 비교는 3번 하면 된다.

log 8 = log 2^3 = 3 

▶ O(n)

[ 예시 ]

void printArray( int[ ] array )

{

for( int item : array )

{

cout << item << endl;

}

}

array를 받아서 모든 인자를 출력하는 함수의 시간 복잡도는 O(n)이다.

n개의 인자가 있다면 n번 인덱스에 접근할 것이기 때문이다. 

아이템의 개수만큼 접근하는 경우는 o(n)이다.

트리순회, linked list를 순회하는 경우 이러하다.

→기수정렬 -> O(dn), d<4

데이터 자리수를 낮은 자리 수부터 비교하여 정렬해 가는 알고리즘. 

제자리 정렬이 아니라 추가적인 메모리공간이 필요하다. 하지만 크게 소비되지 않는다면 문제없다.

단점은 정렬할 수 있는 데이터타입이 한정되있어서 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되 있어야한다. 부동소수점같은 경우는 적용이 불가. 

▶ O(nlog n)

[ 예시 ]

분할정복 방식으로 설계된 알고리즘들

→머지소트

: 분할정복 방식으로 설계된 알고리즘. 

  큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식. 배열의 크기가 1보다 작거나 같을 때 까지 반복, 

  입력으로 하나의 배열을 받고, 연산 중에 2개의 배열로 계속 쪼개 나간 뒤 합치면서 정렬해 최종 하나의 정렬을 출력함

  분할과정과 합병과정이 나뉘어 진다. 분할과정은 매번 반 씩 감소하므로, logN만큼 반복해야한다.

  각 분할별로 합병을 진행하므로, 합병정렬의 시간 복잡도는 NlogN이다. 

→힙소트 

▶ O(n^2)

[ 예시 ]

2중포문을 도는 경우 발생한다. 

void printArray( int[ ] array )

{

for( firstItem : array )

{

for( secondItem : array )

{

int[ ] orderPair = new int[ ] (firstItem, secondItem );

cout << orderPair <<endl;

}

}

}

→삽입정렬 : 리스트에 한개씩 원소를 삽입함. 맨뒤부터 삽입할 위치를 비교하여 알맞은 위치에 넣어준다. 

→버블정렬 : 자료수의 1개 뺀만큼 루핑을 하면서 서로 인접한 아이템을 스와핑해주는 방법으로 정렬.  2중포문을 돈다.

→선택정렬 : 구현하기가 쉬워서 많은사람들이 구현한다.

minimum value에 가장 작은 수를 순회하면서 넣어준다. 포인터를 앞부터 맨뒤까지 이동하면서 minimum value를 찾아준다. 

6개 아이템이 있으면 6번 비교하니까 36개 비교 . 

→쉘정렬 : 어느정도 정렬된 데이터에 대해서는 상당히 빠르다. 평균적으로는 O(n^1.5)정도로 나타나고 최악의 경우                 O(n^2) 이다. 

< Special Case >

→퀵소트 

: 평균적인 경우에는 nlogn, worse case인경우 O(n^2)의 퍼포먼스를 가진다. 

빅오 표기법은 최악의 경우를 표시하므로 퀵소트의 시간복잡도는 사실 O(n^2)이다.

만약 nlogn의 시간복잡도로 말하고 싶다면, 세타nlogn의 시간복잡도를 가진다고 이야기하면 된다. 

 피봇을 정한 후, 리스트를 정한후 피봇보다 큰것은 오른쪽, 작은것은 왼쪽에 배치한다. 

 swap으로 이동하므로 저장공간이 따로 필요없다.

 피봇의 위치를 벽에 놓고, 왼쪽과 오른쪽을 따로 퀵소트로 정렬한다.

각 정렬은 배열의 크기 N 만큼 비교하며, 이를 총 분할깊이인 logN만큼 진행하므로 총 비교횟수는 NlogN 이다. 

다만, 퀵정렬에는 최악의 경우가 존재하는데 이는 배열이 이미 역순이나 정순으로 정렬되어 있는 경우이다. 

이 경우 n번 분할이 이루어지므로 n^2의 시간복잡도를 가지게 된다.

퀵소트가 가장 좋은 알고리즘으로 꼽히는 이유는 따로있다. O(nlogn)에 숨어있는 상수계수의 크기도 작고, 내부정렬이며, 평균적으로 가장 빠르게 수행되는 정렬이다. 가상메모리 상에서도 잘 동작하는 일반적으로 가장 좋은 정렬이다. 

Average case는 대개 계산도 힘들고, 현실에서는 입력되는 값의 정확한 분포를 알기 어려우므로 쓰기 힘들다.

Worst Case는 알고리즘의 성능을 보여주는 척도가 될 뿐 아니라, 경험적으로 알고리즘의 수행시간은 Worst Case의 경우와 수행시간이 큰 차이가 나지 않으므로 일반적으로 시간복잡도를 말할때에는 Worst case기준으로 평가한다. 

대문자 O표기법은 주어진경우의 수행시간의 상한을 나타낸다.