IM Sprint

IM Sprint 시리즈는, 코드 스테이츠의 웹 개발 심화 코스인 Immersive 코스에서 수강생들과 함께 이야기 나눌 주제에 대해 빠르게 학습하고 정리한 글이다.


Big-O?

[ 빅오(Big-O)표기법 완전정복 | 엔지니어 대한민국 ]
알고리즘의 성능을 수학적으로 표현해주는 표기법으로, 알고리즘의 시간과 공간 복잡도를 표현할 수 있다. 실제 작업에 걸리는 정확한 시간을 표기하는 게 아니라, 어떤 요소들(사용자, 데이터)의 양이 증가할수록 작업 소요 시간이 어떻게 변화하는지를 장기적으로 예측하는 데 사용된다. 정확도보다는 장기적인 변화와 흐름을 보는 게 중요하기 때문에, 그 흐름에 큰 영향을 미치지 않는 상수는 계산 시 무시한다.

1. O(1)

'오원'의 시간복잡도.
데이터의 크기(양)와 상관없이, 작업에 언제나 일정한 시간이 걸림을 뜻한다. 데이터의 양과 상관없이 처리 속도가 일정하다.

const arr = [1, 2, 3];

// 배열 요소의 수와 상관없이, 0번 인덱스의 요소만 확인하므로 시간 복잡도가 일정하다.
const sample = (arr) => {
  return arr[0] === 0 ? true : false;
}

스크린샷 2019-11-19 오전 11.41.54.png

2. O(n)

'오엔' 시간복잡도.
데이터의 크기(양)에 비례해서 처리 시간이 늘어남을 뜻한다. 데이터와 처리 시간이 같은 비율로 증가하기 때문에, 그래프로 나타냈을 때 그려지는 선이 직선이다.

const arr = [1, 2, 3]

// n개의 데이터를 받으면 n번 루프를 도는 코드. arr의 요소수가 n이면 n번 실행된다.
// 즉 n이 늘어나는 대로 정비례하여 처리 시간이 늘어난다.
const on = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i])
  }
}

스크린샷 2019-11-19 오전 11.42.17.png

3. O(n^2)

'오엔스퀘어' 시간복잡도.
데이터가 n개일 때, n * n 만큼 작업 횟수가 소요됨을 뜻한다.
n을 가로와 세로 수치로 가진 사각형의 면적만큼 처리 시간이 걸린다고 상상할 수 있다.
이를 그래프로 나타내 보면 처음에는 데이터의 양이 늘어남에 따라 처리 시간이 조금씩 늘어나다가, 이후에는 큰 폭으로 늘어난다.

const arr = [1, 2, 3];

// 2중 for문. 첫 번째 루프(i)에서 n번 돌면서, 두 번째 루프(j)에서 n번 돌기 때문에 n * n => n^2
// n을 가로와 세로로 한 면적만큼 (여기선 9) 루프를 돌게 된다.
const sample = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(i + j);
    }
  }
}

스크린샷 2019-11-19 오전 11.46.13.png

4. O(nm)

'오엔엠' 시간복잡도.
n개의 데이터와 m개의 데이터를 가지고 작업을 수행할 때, n * m 만큼 작업 횟수가 소요됨을 뜻한다.
n을 가로, m을 세로 수치로 가진 사각형의 면적만큼 처리 시간이 걸린다고 상상할 수 있다.
O(n^2)와 비슷해 보이지만, n은 아주 크고 m은 아주 작을 수도 있기 때문에 반드시 구분해서 표기해야 한다.
그래프는 O(n^2)와 비슷하다.

const arr1 = [1, 2, 3];
const arr2 = [1, 2, 3, 4];

// 2중 for문. 첫 번째 루프(i)에서 n번 돌면서, 두 번째 루프(j)에서 m번 돌기 때문에 n x m
// n을 가로와 세로로 한 면적만큼 (여기선 12) 루프를 돌게 된다.
const sample = (arr1, arr2) => {
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      console.log(i + j);
    }
  }
}

5. O(n^3)

'엔의 세제곱' 시간 복잡도.
데이터가 n개일 때, n * n 만큼 작업 횟수가 소요됨을 뜻한다.
n을 가로와 세로, 높이 수치로 삼은 정육면체(큐빅) 부피만큼 처리 시간이 걸린다고 상상할 수 있다.
O(n^2)보다도 데이터의 증가에 따라 처리 시간이 큰 폭으로 늘어난다.

const arr = [1, 2, 3];

// 2중 for문. 첫 번째 루프(i)에서 n번 돌면서, 두 번째 루프(j)에서 n번, 세 번째에서 n번 돌기 때문에 n^3
// n을 가로와 세로, 높이로 한 정육면체(큐빅) 부피만큼 (여기선 27) 루프를 돌게 된다.
const sample = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      for (let k = 0; k < arr.length; k++) {
        console.log(i + j + k);
      }
    }
  }
}

스크린샷 2019-11-19 오전 11.47.57.png

6. O(2^n)

'2의 n승' 시간 복잡도.
n개의 데이터가 있을 때, 작업이 한 번 호출될 때마다 내부적으로 2번씩 작업을 수행하게 되는 구조를 뜻한다.
2번씩이 아닌 m번씩(3, 4, 5번….) 수행할 때는 O(m^n)의 복잡도를 가진다고 표현한다.
O(n^3)보다도 데이터의 증가에 따라 처리 시간이 큰 폭으로 늘어난다.
스크린샷 2019-11-19 오전 11.49.07.png

7. O(log n)

'오로그엔' 시간 복잡도.
작업이 한 번 수행될 때마다, 처리해야 하는 데이터의 양이 절반으로 줄어드는 알고리즘이 가지는 시간 복잡도.
대표적인 알고리즘은 이진 검색(바이너리 서치 binary search)이다. 맨 앞에서부터 데이터를 찾아 나가는 순차 검색보다 속도가 현저하게 빠르다. 데이터가 증가해도, 처리 시간이 많이 증가하지 않는다.

// 이진 검색 코드
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

const binarySearch = (target, arr, start, end) => {
  if (start > end) {
    return false;
  }
  const center = Math.floor((start + end) / 2);
  if (arr[center] === target) {
    return `값 ${target}는 인덱스 ${center}에 있습니다.`;
  }
  if (arr[center] > target) {
    return binarySearch(target, arr, start, center - 1);
  }
  return binarySearch(target, arr, center + 1, end);
}

const result = binarySearch(6, arr, 0, arr.length - 1);
console.log(result);
// 값 6는 인덱스 5에 있습니다.

바이너리 서치로 배열 안에서 6 찾기

  • 검색 1회차
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9], target = 6
  1. 가장 가운데 값을 찾는다. → 5
  2. 가운데 값을 키값과 비교한다. → 5 === 6 ?
  3. 가운데 값보다 키값이 크면, 찾는 키값은 가운데 값의 오른쪽에 있음을 알 수 있다.
  • 검색 2회차
    arr = [6, 7, 8, 9], target = 6
  1. 가장 가운데 값을 찾는다. → 7
  2. 가운데 값을 키값과 비교한다. → 7 === 6?
  3. 가운데 값보다 키값이 작으면, 찾는 키값은 가운데 값의 왼쪽에 있음을 알 수 있다.
  • 검색 3회차
    arr = [6], target = 6
  1. 검색 완료 → 6 === key
    스크린샷 2019-11-19 오전 11.50.27.png

데이터 구조 별 작업 시간 복잡도

1. Array

배열은 메모리상에서, 데이터 사이에 빈 곳이 없이 데이터가 들어차 있는 형태를 말한다(자바스크립트의 배열은 예외다). 코드로 배열 사이즈를 정해주면, 정해진 크기가 한 번에 연속해서 들어갈 만한 공간을 컴퓨터 메모리상에서 찾아 확보하여 할당한다.

  • Lookup : 특정 인덱스에 위치한 데이터 가져오기
    이미 데이터 위치를 알고 있으므로, 즉각 데이터에 접근할 수 있다. 데이터의 양과 상관없이 항상 같은 시간이 걸린다. O(1)

  • Assign : 특정 인덱스에 위치한 데이터를 새로운 데이터로 바꿔넣기
    이미 위치를 알고 있고, 데이터를 새로운 자리에 삽입하는 것이 아닌 기존에 마련된 위치에 바꾸어 넣는 것이기에 데이터가 아무리 많더라도 항상 같은 시간이 걸린다. O(1)

  • Insert : 새로운 데이터를 기존 데이터 사이에 삽입하기
    특정 위치에 데이터를 삽입하려고 하면, 그 위치를 기준으로 오른쪽에 있는 모든 데이터의 인덱스를 +1 해서 자리를 이동 시켜 공간을 확보해야 한다. 그러므로 데이터가 많을수록 정비례해 처리 시간이 늘어난다. O(n)

  • Remove : 데이터를 제거하기
    특정 위치의 데이터를 제거하고 나서, 그 위치를 기준으로 오른쪽에 있는 모든 데이터의 인덱스를 -1 해서 자리를 이동 시켜 빈 곳이 없도록 만들어야 한다. 그러므로 데이터가 많을수록 정비례해 처리 시간이 늘어난다. O(n)

  • Find : 데이터가 위치한 인덱스를 모르는 상태에서, 원하는 데이터를 찾기
    데이터의 위치를 모르기 때문에, 첫 인덱스부터 마지막 인덱스까지 돌며 데이터를 찾아야 한다. 찾는 데이터가 가장 앞에 위치한다면 O(1)의 시간 복잡도가 걸리겠지만, 그럴 확률은 높지 않기 때문에 평균적으로 데이터를 찾을 땐 데이터가 많을수록 정비례해 처리 시간이 늘어난다. O(n)

2. Linked List

링크드 리스트는 한 노드(데이터)가 다음 노드의 위치를 알고 있다. 그래서 배열과는 다르게 어떤 공간에 데이터들이 연속해서 모여 있을 필요가 없다. 만약 어떤 노드가 다른 노드와의 연결이 끊어져서 전혀 찾아갈 수 없게 된다면, 자동으로 가비지컬렉터가 그 노드를 회수한다.

  • Lookup : 특정 인덱스, 순번에 위치한 데이터를 찾아 가져오기
    데이터 검색 시작은 링크드 리스트의 가장 첫 노드인 HEAD 노드에서 출발한다. 그곳에서 가르키는 다음 노드의 위치를 따라, 원하는 횟수만큼 이동하여 데이터를 찾는다. 그러므로 데이터의 숫자가 많아지면 많아질수록, 정비례해 처리 시간이 늘어난다. O(n)

  • Find : 순번을 모르는 상태에서 데이터를 찾기
    Lookup과 마찬가지로, 첫 노드인 HEAD에서 출발하여 원하는 데이터가 나올 때까지 순서대로 다음 노드들을 살펴봐야 하기에 데이터의 양이 많아질수록 작업 시간이 늘어난다. O(n)

  • Assign : 특정 인덱스, 순번에 있는 노드에 데이터를 바꿔넣기
    이 역시 Lookup과 마찬가지로, HEAD에서 출발하여 찾는 순번의 노드까지 전진한 후 그곳에서 데이터를 바꿔 넣는다. 그래서 데이터의 양이 많아질수록 작업 시간이 늘어난다. O(n)

  • Insert : 새로운 데이터를 기존 데이터 사이에 삽입하기

    • 링크드 리스트의 머리(HEAD)와 꼬리(TAIL)로 노드를 삽입한다면 :
      링크드 리스트는 HEAD 노드와 TAIL 노드의 위치 정보를 기억하고 있다. 그래서 HEAD와 TAIL 노드에 바로 접근할 수 있기 때문에, 데이터의 양과 상관없이 항상 일정한 시간이 걸린다. O(1)

    • 링크드 리스트의 중간에 삽입할 때 :
      Lookup과 마찬가지로, 데이터를 삽입하기 위해 원하는 위치까지 찾아 들어가는 데 드는 시간은 O(n) 이다. 그리고 삽입 그 자체를 수행하는 시간은 O(1) 이다. 배열과는 달리 데이터를 새로 삽입한 후에, 그 오른쪽으로 이어지는 다른 데이터들의 인덱스를 변화시킬 필요가 없기 때문이다.
      그리고 삽입 작업을 할 때는 이미 데이터를 삽입하기를 원하는 위치를 알고 있는 경우가 많다. 그래서 바로 삽입이 가능하고, 별도로 다른 데이터들의 정보를 바꿀 필요가 없기 때문에 보통 링크드 리스트의 Insert 시간 복잡도를 O(1) 이라고 말한다.

  • Remove : 데이터를 제거하기

    • 링크드 리스트의 머리(HEAD)혹은 꼬리(TAIL) 노드를 지운다면 :
      링크드 리스트는 HEAD 노드와 TAIL 노드의 위치 정보를 기억하고 있다. 그래서 HEAD와 TAIL 노드에 바로 접근할 수 있기 때문에, 데이터의 양과 상관없이 항상 일정한 시간이 걸린다. O(1)

    • 링크드 리스트의 중간에 위치한 노드를 제거할 때 :
      Lookup과 마찬가지로, 데이터를 삽입하기 위해 원하는 위치까지 찾아 들어가는 데 드는 시간은 O(n) 이다. 그리고 삭제 그 자체를 수행하는 시간은 O(1) 이다. 배열과는 달리 데이터를 새로 삽입한 후에, 그 오른쪽으로 이어지는 다른 데이터들의 인덱스를 변화시킬 필요가 없기 때문이다.

    • 그런데 Remove는 Insert와는 달리 보통 시간 복잡도를 O(1)이라고 말하지 않는다 :
      링크드 리스트에서 노드를 삭제할 때는, 내가 삭제하려는 노드 위치를 알고 있다 하더라도 검색 시간이 걸린다. 왜냐하면 링크드 리스트에서 노드를 '삭제'한다는 것은, 삭제하려는 노드의 이전 노드가 가진 포인터를 삭제하려는 노드의 다음 노드를 향하도록 바꾸는 작업이다. 그래서 반드시 삭제하려는 노드의 '이전 노드'가 어디에 있는지를 알아야 한다.
      삭제하려는 노드는 '다음 노드'의 위치를 알고 있을 뿐 '이전 노드'의 위치는 알지 못하기 때문에, 어쩔 수 없이 HEAD부터 검색을 통해서 삭제하려는 노드의 '이전 노드'를 알아내야 한다. 그래서 검색 시간이 작업 시간에 항상 포함되어 시간 복잡도는 O(n) 이다.

    • 하지만 만약 더블 링크드 리스트(Doubley Linked List)라면? :
      더블 링크드 리스트는, 노드가 자신의 앞 노드와 뒤 노드의 위치를 모두 알고 있다. 그렇다면 삭제하고자 하는 노드의 위치를 알고 있으면 해당 노드의 이전 노드를 찾기 위해 HEAD부터의 검색이 필요 없다. 이 때 시간 복잡도는 O(1) 이다.

3. Tree / Binary Search Tree

트리는 정점에 위치한 노드인 Root노드를 가지고 있으며, 구조에 포함된 모든 노드가 자신의 데이터와 나와 이어진 자식 노드의 위치 정보를 가지고 있다. 자식 노드끼리는 서로의 위치 정보를 모른다.

원하는 데이터가 어디에 있는지 찾고 지우고 삽입하기

1. 일반적인 트리(예, DOM트리)

일반적인 트리 구조는 부모 노드에 자식 노드가 0개부터 n개까지 다양하게 연결되어 있고, 노드들이 데이터값과 상관없이 배치된 구조이다.


데이터 검색은 Root노드부터 시작한다. 어떤 노드에 접근하려면 그 부모 노드를 통해서만 가능하므로, Root노드부터 시작하여 그 자식 노드를 살피고, 없다면 또 그 자식 노드를 살피는 식으로 검색하여 최악의 경우 모든 노드를 살펴보아야 한다. 그래서 데이터 수(노드 수)가 늘어나는 만큼 작업 시간도 늘어난다. O(n)

2. 바이너리 서치 트리

바이너리 서치 트리는 부모 노드에 자식 노드가 0개부터 2개까지만 연결되어 있고, 부모 노드의 왼쪽 자식 노드에는 부모보다 작은 값이, 오른쪽에는 큰 값이 들어가 있는 구조다.


바이너리 서치 트리는 노드의 왼쪽 자식 노드에는 자신보다 작은 값이, 오른쪽에는 큰 값이 들어가 있음이 보장되어 있다. 그래서 Root 노드에서 검색을 시작하여 값을 비교해가면서 '검색하지 않아도 괜찮은 자식 노드'가 무엇인지를 판단할 수 있다. 그래서 한 번 검색할 때마다 검색할 노드의 양이 1/2로 줄어든다. O(log n)

최악의 경우? : 바이너리 서치 트리의 데이터 구조가, 오른쪽으로만 치우쳐 있거나 왼쪽으로만 치우쳐 있을 때는 결국 모든 데이터를 돌아보게 된다. 이 때는 O(n)

바이너리 서치 트리에서 데이터 검색하기와 바이너리 서치(어레이)

두 작업은 같은 시간 복잡도 O(log n)을 가지고 있지만, 데이터가 메모리에 저장된 모습이 다르다.
어레이는 데이터들이 연속되게 존재해야 하지만, 트리 구조는 그렇지 않다. 그래서 메모리 사용 효율 면에서는 바이너리 서치 트리가 선호된다.

배열, 링크드 리스트, 더블 링크드 리스트 비교

  • 배열 : 데이터를 찾고, 바꿔 넣는 데는 빠르지만, 삽입/삭제 시 느리다.
  • 링크드리스트 : 삽입이 빠르지만, 데이터를 찾고 삭제하는 데는 느리다.
  • 더블 링크드 리스트 : 삽입 삭제가 빠르지만, 양쪽노드 위치를 가지고 있기 때문에 노드 하나가 다른 구조에서의 데이터보다 데이터를 더 많이 차지한다.