BigO 표기법이란?

• 알고리즘의 성능을 수학적으로 표현해주는 표기법
• 알고리즘의 시간,공간 복잡도를 표현
• 데이터나 사용자의 증가율에따른 알고리즘 성능 예측

---

BigO 표기법의 예시

O(1)-constant time

• 입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘

  O(1)의 Code
  
  O(1)의 time graph
  

O(n)-linear time

• 입력 데이터 크기에 비례한 알고리즘

  O(n)의 Code
  
  O(n)의 time graph
  

O(n^2)-quadratic time

• 입력 데이터를 첫 루프 , 두번째 루프

  O(n^2)의 Code
  
  O(n^2)의 structure
  
  O(n^2)의 time graph
  

O(nm)-quadratic time

• n을 m만큼 루프 도는것

  O(nm)의 Code
  
  O(nm)의 structure
  
  O(nm)의 time graph
  

O(n^3)-polynomial / cubic time

• n 루프가 3번

  O(n^3)의 Code
  
  O(n^3)의 structure
  
  O(n^3)의 time graph
  

O(2^n)-exponential time

• 피보나치 수열
• 함수마다 두번씩 재귀 함수 호출을 트리의 높이만큼 반복

  O(2^n)의 Code
  
  O(2^n)의 structure
  
  O(2^n)의 time graph
  

O(m^n)-exponential time

• 2대신 m만큼 반복

O(log n)

• 대표적인 예시 : 2진 검색 (키 값과 비교하여 작거나 크면 앞뒤숫자 제거)
• 한번 처리가 진행될 떄마다 검색하는 데이터의 양이 절반씩 떨어지는 알고리즘
• 데이터가 증가해도 성능의 차이가 크게 나지 않음

  O(logN)의 Code
  
  O(logN)의 structure
  
  O(logN)의 graph
  

O(sqrt(n))-square root n

• 위의 한줄이 제곱근
• 정사각형에 n을 다 채워서, 맨위의 한줄만 돌리는 알고리즘

  O(sqrtN)의 structure
  

Big O표기법의 중요한 점

• 데이터 처리시간 증가율을 예측한다.
• 상수는 고정 숫자라 증가율에 고정된 상수만큼 영향을 미친다. 증가하지 않는 숫자는 신경쓰지 않는다.