[Big O] 미래를 내다보고 코드를 효율적으로 짜자

Big O는 Input이 증가함에 따라 연산의 양이 얼마나 더 많이 증가하는지를 나타내는 지표로, 알고리즘의 성능을 나타낸다.

 

<확장성에 따른 성능이 좋은 순>

O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!)

*언제나 절대적이지는 않다. 예를 들어 배열이지만 길이가 정해진 경우에는 상황에 따라 O(n) 알고리즘이 O(1) 알고리즘보다 더 성능이 좋을 수 있다.

*JavaScript에서 문자열의 .length는 O(1)이다.

*그렇다고 확장성만 따질 것은 아니고, 가독성 또한 좋아야 한다.

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

<Big O Notation 공식의 규칙>

 

1. 가장 최악의 복잡도를 활용할 것.

만약 배열이라면 미래에 Input이 어떻게 변형될 지 알 수 없기 때문에, 현재 첫번째 원소라고 O(1)이 아니라 가장 마지막 원소까지 탐색하는O(n)으로 사용한다.

*for 루프라고 모두 O(n)이 아니다. 루프의 상한이 상황에 따라 push가 가능한(가변적인) 배열이 아니라 아래처럼 상수로 정해져있고 그 안에 단순한 연산뿐이라면 O(1)이다.

// O(1)
let i = 0;
for ( ; i < 100; i++ ) {
  console.log("Hello");
}

2. 최고차항의 n만 신경쓰고 계수와 상수는 무시할 것.

상대적으로 너무 미미하기 때문이다.

3. 한 파일에 여러 데이터가 들어갈 경우, 각 Big O를 구하여 합산한다.

예를 들어 어떤 함수에 첫째 인자가 길이가 10인 배열이고, 둘째 인자가 길이가 단 1인 배열이라고 해보자.

이때 함수 내부에서 첫째 인자 배열과 둘째 인자 배열이 병렬로 for 루프를 돈다면 O(a+b)이지만 , 품고 있다면 O(a * b)이다.

 

---

나의 웹사이트가 미래에 대박이 나서 유저수가 급증하면, 그들이 만들어내는 데이터는 폭증할 것이고, 그것을 관리하고 로딩하고 처리하려면 두말할 필요 없다.

 

초창기 또는 토이프로젝트에서는 이러한 알고리즘의 성능을 몸소 느끼기 힘들기 때문에 별 신경을 안 쓸 것이다.

하지만 이제는 알고리즘을 공부함으로써 성능을 중시하게 되고, 이는 1초 딜레이라도 참지 못하는 유저들의 사용자 경험을 높여줄 것이다.

 

자료구조는 데이터를 저장하는 방식이며, 알고리즘은 그 자료구조를 사용하는 방식이다.

자료구조 : 배열, 스택, 큐, 연결리스트, 트리, 그래프, 해시테이블

알고리즘 : 정렬, 다이나믹 프로그래밍, BFS + DFS 검색, 재귀

 

우리 프로그래머는 좋은 자료구조와 좋은 알고리즘을 이용하여 시간복잡도와 공간복잡도를 줄이는 최적의 조합점을 찾아, 사용자에게 최고의 프로그램을 설계해야 할 것이다.

그리고 프로그램을 가독성이 좋고(Readable) 확장성이 좋은(Scalable) 코드로 작성해보도록 하자!