📖 빅 오 표기법 (Big O Notation)

코딩테스트를 풀고나서 다른 사람의 코드를 보면 와 이 사람 코드 진짜 복잡하게 짰네 하고 생각이 들때가 있고, 와 이 사람 코드 간결하다~ 싶을 때가 있다.

사실 니가 잘 짰니 내가 잘 짰니를 정하는 건 이런 내 주관이 아니라 '객관'에 의해서 평가가 되어야 하는데, 이렇게 알고리즘을 비교 평가 하기 위해 만들어 진 것이 빅 오 표기법이다.

📌 빅 오 표기법이란?

빅 오 표기법은 앞서 말했듯, 알고리즘 성능을 평가 하기 위한 표기법이다.
그런데 왜? 빅 오 표기법을 사용해야 할까? 이는 다음과 같이 이야기 할 수 있을 것 같다.

1. 정확한 용어를 통해 알고리즘 성능 표기가 가능해진다.
2. 여러 접근법들의 trade-off에 대해 이야기 하기 좋아진다.
3. 코드에서 비효율적인 부분을 찾는 것이 쉬워진다.

즉, 빅 오 표기법을 통해 Better Code를 찾아 가는 것에 목적이 있다.

그렇다면 과연 Better Code의 기준은 무엇일까?
우리는 흔히 1. 실행이 빠르고 2. 메모리를 적게 사용하고 3. 코드가 간결한 것을 생각 하게 된다.

📌 시간 복잡도

실행이 빠른 것은, 어떻게 알 수 있을까?

아마도 코드 내에서 시간을 재볼 수 있을 것이다. 시간을 한 번 재보자!

여기 같은 기능을 하는 두 코드가 있다.

코드 1

function addUpTo(n) {
  return n * (n + 1) / 2;
}

const time1 = performance.now();
addUpTo(1000000000);
const time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)

코드2

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

const t1 = performance.now();
addUpTo(1000000000);
const t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)

여기서 performance.now()은 DOMHighResTimeStamp에 접근해, 페이지가 로드된 이후로 지난 ms를 보여준다.

위 아래는 각각 첫번째 코드와 두번째 코드를 실행했을 때의 결과 값이다.
같은 기능을 하더라도 실행 시간의 차이가 나는 것을 볼 수 있다.

그런데 실험 삼아 각 코드를 한번 씩 더 실행했더니, 이전과 다른 값이 출력 되었다. 코드 기분이 안좋았나본뎅

사실 이렇기 때문에 코드 내에서 시간 측정하는 방법은 추천되지 않는다.

1. 기기 사양 혹은 브라우저 마다 다르게 측정이 된다.
2. 같은 기기라 하더라도 위 처럼 다르게 측정된다.
3. 정말 빠른 알고리즘에서는 너무 짧은 시간에 모듯것이 끝나는데, ms단위로 측정하는 performance.now()같은 function이 이 차이를 잡아 내지 못하면 무의미하다.

이럴때!!! 측정하는 것이 시간 복잡도다.
시간 복잡도 단어 자체에는 '시간'이 들어가지만, 사실 우리가 생각하는 시간이 아니라, '연산의 갯수'에 포인트가 있다.

시간 복잡도는 input이 늘어날 수록 실행시간이 변하는 것(입력 크기와 실행시간의 관계)을 나타낸다. 이때 Big O는 연산 갯수가 몇개인지와 같이 세부적인 내용보다는 전반적인 추세를 파악한다.

N에 따라 실행시간이 가질 수 있는 최대값 그래프를 그려보는데, 우리가 Big O 표기법에서 고려하는 그래프는 다음 다섯 가지다.

처음 보는 사람이라면 그래서 이걸 어떻게 알 수 있는데? 라고 생각할 것이다.

그치만 코드를 보고 좀 더 빠르게 빅 오 표기법으로 나타낼 수 있는 방법이 있다.

1. 변수 할당, 단순 연산(더하기, 빼기, 곱셉, 나눗셈)은 O(1)
2. index와 key를 통한 배열과 객체에 접근하는 것은 O(1)
3. 반복문은 보통적으로 O(N), 중첩 반복문은 얼마나 중첩되었느냐에 따라 O(N^m)

이때 O(1)의 1은 연산의 갯수가 하나라는 것이 아니라 상수의 의미로, 일정하다~라고 생각하면 된다.

위의 방법을 사용해 다음 코드의 시간 복잡도를 나타내보자.

function addUpToFirst(n) {
  let total = 0;
  for (let i = 0; i <= n; i++) {
    total += i;
  }
  return total;
}

변수 할당했고... 단순 연산도 했고,,,했는데 for문이 있다. n+어쩌고여도 우리는 전반적인 추세를 보자고 했으므로 n만 남긴다. 위 코드의 시간 복잡도는 O(n)이다.

function addUpToSecond(n) {
  return n * (n + 1) / 2;
}

연산을 곱하기 더하기 나누기 한 세 번 했는데 그럼 O(3)? 아니다. 우리는 전반적인 추세를 보자고 했다. 위 코드의 시간 복잡도는 O(1)이다.

function printAllPairs(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}

for문이 중첩되어있다. O(N^2)다.

function logAtMost5(n){
    for (let i = 1; i <= Math.min(5,n); i++) {
      console.log(i);
    }
}

for문이 있다. O(N)이다.

사실 shorthands만 보고 계산하면 안된다라는 예시를 위한 코드다. for문에서 i가 계속 증가해도 Math.min()에 의해 5이상이 되더라도 i는 5가 최대이므로 전반적인 추세를 보면 n이 아무리~~~ 커져도 그래프는 O(1)처럼 상수 그래프를 그리게 될 것이다. 위 코드의 시간 복잡도는 O(1)이다.

📌 공간 복잡도

그렇다면, 메모리를 적게 사용하는 코드는 어떻게 비교하고 알 수 있을까?

이럴때 고려할 것이 공간 복잡도라고 할 수 있겠다.
공간 복잡도는 입력에 필요한 공간을 제외하고, 알고리즘이 필요로 하는 메모리 공간을 비교한다.

공간 복잡도의 계산에는 다음과 같은 규칙이 존재한다.

1. 원시타입(null, boolean, 숫자, undefined)은 대부분 상수 공간 O(1)이다.
2. 문자열은 O(N)의 공간이 필요하다.
3. 참조타입도 O(N)이 필요하며, 이때 N은 배열의 길이나 객체의 키 갯수일 수 있다.

다음 코드를 살펴보자.

function sum(arr){
	let total = 0;
    for(let i =0; i<arr.length; i++){
    	total += arr[i];
    }
    return total;
}

위 코드에서, total변수에 값을 초기화하고 i에 값을 초기화 하는 등은 상수 공간, 즉 O(1)을 차지한다. 항상 같은 공간을 차지한다.

function double(arr){
	let newArr = [];
    for(let i =0; i<arr.length; i++){
    	newArr.push(2*arr[i]);
    }
    return newArr;
}

위 코드에서는 arr를 2배로 늘려 newArr에 push연산 해주는데, 이때 차지하는 공간은 입력된 배열의 크기와 비례한다. 그러므로 O(N)이다.

📌 객체의 Big O

이번에는 객체 연산, 객체 메소드에 대한 시간 복잡도에 대해 알아보자.

객체는 언제 사용할까?
우리는 객체를 정렬이 필요하지 않을때, 빠른 접근, 삽입과 삭제 연산이 필요할때 사용할 수 있다. 여기서 '빠르다'는 것은, 시간 복잡도가 O(1)임을 의미한다.

객체 연산의 시간 복잡도
1. 삽입 - O(1)
2. 삭제 - O(1)
3. 탐색 - O(N)
4. 접근 - O(1)

객체는 정렬이 필요하지 않고, 키를 통한 접근이 이루어지므로 삽입, 삭제, 접근 연산이 O(1)으로 일정하다.

탐색은 어떤 특정 정보가 어떤 값에 있는지를 확인하는 것을 말하는데, 키 값이 늘어날 수록 걸리는 시간이 늘어나 O(N)이 된다.

객체 메소드의 시간 복잡도
1. Object.keys() - O(N)
2. Object.values() - O(N)
3. Object.entries() - O(N)
4. hasOwnProperty() - O(1)

Object.keys()는 객체의 키-값이 늘어날 수록 배열에 추가할 키가 늘어나므로 O(N)이다.
Object.values()는 객체의 키-값이 늘어날 수록 배열에 추가할 값이 늘어나므로 O(N)이다.
Object.entries()는 객체의 키-값이 늘어날 수록 배열에 추가할 키-값이 늘어나므로 O(N)이다.
hasOwnProperty()는 키를 통해 값이 있는지 없는지를 접근하므로 N이 늘어나도 같은 시간복잡도를 가지므로 O(1)이다.

📌 배열의 Big O

이번에는 배열 연산, 배열 메소드에 대한 시간 복잡도에 대해 알아보자.

그렇다면 배열은 언제 사용할까?
우리는 배열을 정렬이 필요한 경우에 사용한다. 배열은 접근이 빠르지만, 삽입과 삭제 연산은 성능이 좋지 않을 수 있다.

배열 연산의 시간 복잡도
1. 삽입 - 경우에 따라 다름
2. 삭제 - 경우에 따라 다름
3. 탐색 - O(N)
4. 접근 - O(1)

삽입과 삭제가 경우에 따라 다른 이유는,끝에 삽입 혹은 제거시 O(1)이지만, 맨 앞에서 삽입 삭제 연산이 일어나면 인덱스를 모두 새로 배정해야하므로 O(N)이 된다. 요소의 개수만큼 작업을 해야하기 때문이다.

탐색은 만약 정렬되지 않은 배열의 경우, 배열의 길이가 길어질 수록 탐색 시간이 길어지게 되므로 O(N)이 된다.

배열 메소드의 시간 복잡도
1. Array.push() - O(1)
2. Array.pop() - O(1)
3. Array.shift() - O(N)
4. Array.unshift() - O(N)
5. Array.concat() - O(N)
6. Array.slice() - O(N)
7. Array.splice() - O(N)
8. Array.sort() - O(N*logN)
9. Array.forEach()/map()/filter()/reduce()/...etc - O(N)

push()와 pop()은 앞서 말했듯이 배열의 끝에서 일어나는 삽입과 삭제 연산이다. 이런 경우엔 O(1)이 된다.

shift()와 unshift()은 인덱스를 전부 정해주는 작업이므로 O(N)이 된다.

concat()은 뒤에 붙일 배열의 크기만큼 시간이 늘어나므로 O(N)이 된다.

slice()은 복사하는 요소의 갯수만큼 시간이 늘어나므로 O(N)이다.

splice()은 배열 시작, 끝, 중간 모두에 추가하거나 변경할 수 있는데 인덱스의 변경 작업이 필요하므로 O(N)이다.

📘 참고 자료

https://www.udemy.com/course/best-javascript-data-structures/