[자료구조] 빅오(Big-O)표기법

빅오(Big-O) 표기법  

• 가장 큰 영향력이 있는 항만 표시(영향력 없는 항 무시), 상수항 무시 
• 알고리즘 효율성을 표기해주는 표기법
• 알고리즘 효율성은 데이터 개수(n)가 주어졌을 때, 뎃셈, 뺄셈, 곱셈 같은 기본 연산의 횟수
• 시간 복잡도(시간 효율성), 공간 복잡도(메모리 효율성)
• 크기 : O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(2^n)
  
  • 크기가 작을수록 실행 횟수가 적고 시간 복잡도가 낮음
  • 크기가 클수록 실행 횟수가 많고 시간 복잡도가 높음

빅오 표기법 그래프

빅오 표기법 예제
1. O(1) : 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸림

• hash

2. O(N) : 입력 데이터의 크기에 비례해서 시간이 소요

3. O(N²) : 입력 데이터의 크기에 제곱에 비례해서 시간이 소요

4. O(logN) :

• 이진 탐색

5. O(NlogN) 
6. O(2^n)