📘 Data Structure w/ hoonnotes

Preface

📌 개발 공부 9개월 차인 to-be 개발자의 자습 blog🙂ﾠMar 27 ~ 02, 2022

현재 상태
간단 개념에 더해 깊이 있는 내용 학습 시작 1

Summary

시간 복잡도와 공간 복잡도를 통해 code가 동작될 때의 구동 속도가 얼마나 빠른지, 얼마나 memory 공간을 차지하는지 설명할 수 있다. 하지만 JavaScript로는 공간 복잡도를 다루기에 적절하지 않으므로 시간 복잡도만 다루기로 한다.

🧐❓ 왜 공간복잡도를 다루기에 적절하지 않지? JavaScript는 memory 사용같은 걸 개발자가 하는 게 아니라 JavaScript가 알아서 해주기 때문에 그런가? 🧐

Big-O Notation

code의 효율성을 수학적으로 표현하는 것이다.
ref. Ω (omega), Θ (theta), Ο (omicron)
시간 복잡도는 도출하고자 하는 값이 어디에 있는지, 어떻게 찾는지에 따라 best case와 worst case가 있는데 Big-Ο는 worst case를 기준으로 한다.

🧐❓ 설명이 다르다. 노마드 코더님은 평균을 기준으로 한다고 했는데! 다른 설명을 찾아보니

• best case : Big-Ω Notation
• average case : Big-Θ Notation
• worst case : Big-O Notation

라고 하며 가능하면 worst casee를 기준으로 programming하는 것이 만약을 대비하기 좋다고 한다. 🧐

운이 좋게 결과를 빠르게 도출할 수 있겠지만 실제 service를 구현할 땐 보수적으로 접근하는 것이 안전하기 때문에 worst case를 기준으로 생각하는 것이 좋다.

※ 성능에 큰 영향을 주지 않으므로 상수는 무시한다.
    e.g. O(2N) → O(N), O(N⁴) → O(N²)

(1) O(N)

input (문제의 크기) 만큼 소요 시간이 늘어난다.
ref. arr.shift(), arr.unshift(), arr.splice()

// 🎵 n만큼 실행
const logItems = (n) => {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
};

logItems(7);

// ⬇️ Output
// 0
// 1
// 2
// 3
// 4
// 5
// 6

// 🎵 2n만큼 실행
const logItems = (n) => {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
  for (let j = 0; j < n; j++) {
    console.log(j);
  }
};

logItems(7);

// ⬇️ Output
// 0
// 1
// 2
// 3
// 4
// 5
// 6
// 0
// 1
// 2
// 3
// 4
// 5
// 6

(2) O(N²)

input (문제의 크기) 만큼 소요 시간이 기하급수적으로 늘어난다.
비효율적인 풀이법이다.

// 🎵 4^2 (4*4) 만큼 실행 (n^2 (n*n))
const logItems = (n) => {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
};

logItems(4);

// ⬇️ Output
// 0 0
// 0 1
// 0 2
// 0 3
// 1 0
// 1 1
// 1 2
// 1 3
// 2 0
// 2 1
// 2 2
// 2 3
// 3 0
// 3 1
// 3 2
// 3 3

// 🎵 4^3 (4*4*4) 만큼 실행 (n^3 (n*n*n))
const logItems = (n) => {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        console.log(i, j, k);
      }
    }
  }
};

logItems(4);

// ⬇️ Output
// 0 0 0
// 0 0 1
// 0 0 2
// 0 0 3
// 0 1 0
// 0 1 1
// 0 1 2
// 0 1 3
// ... (너무 길어서 생략)
// 3 2 0
// 3 2 1
// 3 2 2
// 3 2 3
// 3 3 0
// 3 3 1
// 3 3 2
// 3 3 3

하나의 함수에 O(N²)와 O(N)이 함게 있어 'O(N²)+O(N)'으로 표현할 수 있을 때, 자료가 클 수록 O(N²)의 영향이 크므로 O(N)을 생략하고 O(N²)로만 표기한다.

// 🎵 O(N²)+O(N) → O(N²)
const logItems = (n) => {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
  for (let k = 0; k < n; k++) {
    console.log(k);
  }
};

logItems(4);

(3) O(1)

숫자가 얼마나 커지든 한 번의 작업만 하는 logic이다.
e.g. (JavaScript는 아니지만) arr.get[3] : index 3에 해당하는 원소 찾기
constant라고도 표기한다.
가장 빠르게 연산할 수 있다.
ref. arr.push(), arr.pop()

// 🎵 한 번만 계산
const addItems = (n) => {
  return n + n;
};

addItems(4);

(4) O(logN)

네 가지 중 O(1) 다음으로 가장 효율적이다.
e.g. log₂1,073,741,824를 31회만에 연산할 수 있다.

Doubly Linked List

LinkedList는 head와 tatil을 pointer로??? 가지고 있다??? 그래서 class의 pointer 개념이 필요한 거임

값이 7 하나만 있을 때

class Node {
  constructor (value) {
    this.value = value;
    this.next = null;
  }
}

class Node {
  constructor (value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DbLinkedList {
  constructor (value) {
    const newNode = new Node (Value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
}

---

Endnote

🔗 related documents

소프트웨어 어휘다지기 - 중등 - 시간 복잡도

🙇 the source of this content

hoonnotes - [자료구조]