Big-O 표기법(annotation)

1. Big-O(빅오) 표기법 - 알고리즘의 성능 및 복잡도를 표현하기 위하여 사용하는 지표 - 알고리즘의 실행 시간 또는 사용 메모리 공간을 표현 - 정확한 값이 아닌 어림 값으로, 알고리즘의 대략적인 평가만 가능 - 유사한 다른 표기법으로는 Big-Ω(빅오메가), Big-Θ(빅세타) 표기법이 있음
2. Big-O(빅오)? Big-Ω(빅오메가)? Big-Θ(빅세타)?
   - Big-O: 알고리즘의 최악의 상태를 나타냄(가장 느린 경우)
   - Big-Ω: 알고리즘의 최상의 상태를 나타냄(가장 빠른 경우.
   - Big-Θ: 알고리즘의 평균의 상태를 나타냄(중간) - 알고리즘 측정 시 최악의 상태보다 빠르다는 것이 확실히 보장므로 Big-O 사용 - 다른 것을 사용했을 경우에는 확실한 보장은 아님
3. 시간복잡도, 공간복잡도
   - 시간복잡도 1) 알고리즘의 실행 속도를 측정(CPU)
   2) 표기법은 (4.표기법 및 종류) 참고 3) O(n2)포함해서 더 느린 알고리즘은 좋지않다고 판단 - 공간복잡도 1) 알고리즘이 사용한 메모리를 측정(RAM) 2) 크기가 N인 배열이 N*N배열 되었을 경우 공간 복잡도는 N2
   - 현재는 빅데이터 처리 이슈들이 많아, 공간복잡도도 많이 생각 함
4. 표기법 및 종류

O(1): 상수형	O(logN): 로그형	O(N): 선형
O(N logN): 선형 로그	O(N2): 제곱	O(N3): 3제곱
O(2N): 2의 n 제곱	O(N!): 팩토리얼


<그림1. 표기법 및 종류>
(http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation)





5. 측정 방법 및 유의사항 - 측정 방법 1) 알고리즘에서 코드가 몇 번 실행 되는지 측정 2) 상수는 1로 표시, 지수는 가장 큰 차수만 표시(N이 커지면 무시해도 될만한 작은 수 이므로) 3) Ex: 2n2 - n + 1 = O(n2) - 유의사항
      1) 측정 대상의 데이터 구조(array, set, dictionary, hash 등)에 따라 다르게 생각할 수 있음
      2) set, dictionary, hash의 경우는 key값을 이용하여 접근하고 같은 키에 값이 들어올 경우 덮어 씌움
      3) 데이터 구조에 따른 탐색, 삽입, 삭제 등의 속도가 다름(각 구조의 동작 방식을 기본으로 알아야 함)
   
   
   
6. 유명 정렬 알고리즘들의 성능.
   - 버블정렬, 선택정렬, 삽입정렬: O(N2)
   - 퀵정렬: O(N logN), 이미 정렬이 다 되어있는 경우에는 O(N2)
   - 합병정렬 : O(N logN), 공간이 많이 필요함.
   - 정렬 방법 및 정렬 상태에 따라서 성능이 다른 경우(퀵정렬)가 있으므로 상황에 따른 측정능력 필요