알고리즘 A가 알고리즘 B보다 안정성이 높다. 그렇지만, 알고리즘 B도 남겨두는 것이 좋다. 안정적인 성능을 보장하는 알고리즘은 보다 구현의 난이도가 높기 때문이다.
따라서, 상황에 맞게 알고리즘을 선택하는 것이 중요하다.

빅-오 표기법

빅-오란, T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다.

ex) T(n) = n^2 + 3n + 1
     T(n) = n^2 : 가장 영향력이 큰 n^2만 남겨둔다.
     O(n^2) : 빅-오 표기법

• O(log n): 데이터 수가 2, 3, 4로 늘어날 때 연산횟수는 4, 8, 16 으로 두배씩 늘어난다.
• O(n): 데이터 수 == 연산횟수
• O(nlog n): 데이터수가 2배로 늘어날 때, 연산횟수는 두배를 조금 넘게 증가한다.
• O(n^2): 데이터 수 == 연산횟수^2 (반복문이 두 번 있는 케이스)
• O(n^3): 데이터 수 == 연산횟수^3

빅-오 표기법 성능 비교

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

빅-오 표기법 몇 가지 예제

1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리, 배열탐색
3. O(n) : for 문
4. O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬
5. O(n^2): 이중 for 문, 삽입정렬, 거품정렬, 선택정렬