[기술 면접 준비] BigO 표기법

[기술 면접 준비] BigO 표기법

BigO 표기법

📌참고 자료

• 빅오 표기법 (big-O notation) 이란 | 인생의 로그캣
• [알고리즘] 빅오,빅세타,빅오메가와 공간복잡도에 대하여 알아보자 | Vaert Street

• BigO 표기법이란?
  • 알고리즘의 효율성(시간 복잡도 & 공간 복잡도)를 나타낼 때 사용하는 표기법
• BigO 표기법을 사용하는 이유?
  • 알고리즘의 효율성을 상한선 기준으로 표기하기 때문

• BigO 표기법의 수학적 정의

  n ≥ n0인 모든 n에 대해 f
  (n) ≤ c · g(n)를 만족하는 양의 상수 c와 n0가 존재하면 
  f(n) = O(g(n)) 이다.

• BigO 표기법의 특징
  • 상수항 무시 O(2N) = O(N)
  • 영향력 없는 항 무시 O(N^2 + 2N + 1) = O(N^2)
• BigO 표기법으로 나타낸 알고리즘의 효율성 예)
  • O(1): 스택 push/pop
  • O(log n): 이진 트리
  • O(n): for 문
  • O(n log n): 퀵정렬, 병합정렬, 힙정렬
  • O(n^2): 이중 for문
  • O(2^n): 피보나치 수열