big-O notation

대문자 O 표기법: 계산 복잡도 표현

---

어떤 알고리즘이 문제를 풀기위해 해야하는 계산이 얼마나 복잡한 지를
'계산 복잡도'(complexity) 라고 표현합니다.

여러 계산 복잡도의 표현 방법중 대문자 O 표기법을 가장 많이 사용합니다.

빅오 표기법이라고도 불리는 대문자 O 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 됩니다.

시간 복잡도(time complexity)란 알고리즘의 시간적 효율성을 의미하고
공간 복잡도(space complexity)란 알고리즘의 공간적 즉, 메모리적 효율성을 의미 합니다.

빅오 표기법의 사용이유?

• 알고리즘의 효율성을 상한선 기준으로 표기 하기 때문.
• 추가로 빅 오메가 표기법과 빅 세타 표기법이 있다.
• 빅 오메가 표기법은 알고리즘 효율성을 하한선 기준으로 표기한다
• 빅 세타 표기법은 알고리즘 효율성을 하한과 상한의 중간으로 표기한다.

  주의할점은 빅오 표기법이 상한선만 지정했을뿐 그상한선이 해당 알고리즘의 최악의 성능이라고 단정지을수는 없음.

빅오 표기법의 특징

• 상수항 무시: 필요한 계산 횟수가 입력크기에 정비례 할때에는 상수항을 무시한다.

O(2n) => O(n)으로 취급한다.
함수를 사용할때에도
O(2n+3m+1) => O(n) 으로 취급한다.

• 영향력이 없는 항 무시: 입력값 n에 영향을 받기 때문에 가장큰 n항에만 영향을 받는다.
  

• 빅오 표기법의 성능비교표는 아래와 같다

  

빅오 표기법의 예제 알고리즘

1. O(n) : stack에서 push, pop
2. O(log n): 이진트리
3. O(n) : for 문
4. O(n log n): 퀵정력(quick sort), 병합정렬(merge sort), 힙정렬(heap sort)
5. O(n의제곱): 이중for 문, 삽인정렬(insertion sort), 버블정렬(bubble sort), 선택정렬(selection sort)
6. O(2n의제곱): 피보나치 수열