TIL Big-O 표기법 정리

정의

알고리즘의 효율성을 표기하는 방법중 하나
주로 알고리즘의 시간복잡도와 공간복잡도를 나타내는데 사용된다.
상한선 기준으로 표기한다.(최악의 상황)

특징

1. 상수항 무시 ex) O(2N) -> O(N)
2. 영향력 없는 항 무시 ex) O(N²+2N+1) -> O(N²)

[그래프참고]

비교

O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(2ⁿ)

1. constant O(1) (=fixed 고정된, 변함없는)
   입력사이즈와 관계없이 작업의 수가 일정하다.
   ex) 배열의 push(), pop()

2. logarithmic O(logN) 로그
   작업이 진행될 수록, 작업해야할 입력사이즈가 절반가량 줄어든다.
   ex) 이진트리

3. linear O(N) (직선의)
   입력사이즈에 비례하는(proportional) 작업의 수를 가지고 있다.
   ex) linked-list, for문

4. quadratic O(N²) (이차의)
   ex) 이중 for문

5. exponential O(2ⁿ) (지수의_수학, 기하급수적인)
   ex) 피보나치수열, N-Queens

실제활용

코드를 작성할 때, 시간복잡도를 고려해서 작성하는 것도 좋지만
주니어 개발자는 일단 코드를 작성해내는 것이 우선이다.
시간복잡도는 그 후에 효율적인 코드로 변경할 때 고려하면된다.
우리는 우선 코드작성이 먼저다 !!