개발에서 시간복잡도 계산

개요

• 간단요약하면
  • 반복문 n
  • 2중반복문 n^2
  • 정렬 n log(n)
  • 재귀함수
    • 선형 재귀 (팩토리얼) → O(n)
    • 이진 재귀 (트리 순회) → O(n) ~ O(2ⁿ) (메모이제이션 여부에 따라)
    • 분할정복 (이진탐색) → O(log n)
    • 분할정복 (머지소트) → O(n log n)
• 자주 쓰는 알고리즘

팩토리얼           → O(n)
피보나치 (naive)   → O(2ⁿ)
피보나치 (memo)    → O(n)
이진 탐색          → O(log n)
머지 소트          → O(n log n)
퀵 소트 (평균)     → O(n log n)
순열               → O(n!)
부분집합           → O(2ⁿ)

참고

• 개발에서 log 계산