[개념]시간복잡도 정리

Big-O 기준으로 정리한다. 즉, 최악의 경우를 고려한다!

1. 시간복잡도 효율 순서

Better O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!) Worse

2. 대표 알고리즘

• O(1)
  
  • Stack의 push, pop
• O(log n)
  
  • Binary Search
  • 2의 2제곱부터 n이하의 항목을 출력하는 경우

for (int i = 2; i <= n; i*2) {
    System.out.println(i);
}

• O(n)
  
  • for문
• O(n*log n)
  • Quick Sort, Merge Sort, Heap Sort
• O(n^2)
  • 2중for문
  • 삽입정렬, 버블정렬, 선택정렬
• O(2n)
  • 재귀로 구현하는 피보나치 수열