[CodingTest]시간 복잡도

시간 복잡도

시간 복잡도를 고려한다는 것 - 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

시간 복잡도는 주로 빅-오 표기법을 사용해 나타냄

---

Big-O 표기법

---

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

시간 복잡도를 각각 최악, 최선, 중간(평균)을 나타냄

Big-O 표기법이 가장 자주 사용 - 이 정도 시간까지 걸릴 수 있음을 고려

최악의 경우도 고려하여 대비하는 것이 바람직

---

O(1)

---

• constant complexity(일정한 복잡도)
• 입력값이 증가하더라도 시간이 늘어나지 않음
• 입력값의 크기와 관계없이, 즉시 출력값을 얻을 수 있음

e.g.

const O1 = (arr, index) => {
  return arr[index];
};

console.log(O1([1, 2, 3], 2));

arr이 길어져도 상관없음

---

O(n)

---

• linear complexity(선형 복잡도)
• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가

const On = (n) => {
  for (let i = 0; i < n; i++) {
    // ... 1 초걸림
  }
};
console.log(On(5));

입력값 1이 증가할 때마다 1초 증가

const On = (n) => {
  for (let i = 0; i < 2n; i++) {
    // ... 1 초걸림
  }
};

입력값 1이 증가할 때마다 2초 증가

같은 비율로 증가하고 있다면 5배, 10배로 증가하더라도 O(n)으로 표기

---

O(log n)

---

• logarithmic complexity(선형 로그 시간)
• Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도
• BST(Binary Search Tree)도 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)

O(n2)

---

• quadratic complexity(2차 복잡도)
• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가

function On2(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // ... 1초 걸림
    }
  }
}

n2

function On2(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // ... 1초 걸림
      }
    }
  }
}

n3

---

O(2n)

---

• exponential complexity(기하급수적 복잡도)
• Big-O 표기법 중 가장 느린 시간 복잡도
• 종이를 계속 접는 것처럼..

function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

피보나치 수열

---

데이터 크기에 따른 시간 복잡도

---

정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성

시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측해 보는 것은 중요

데이터 크기 제한	예상되는 시간 복잡도
n ≤ 1,000,000	O(n) or O (logn)
n ≤ 10,000	O(n2)
n ≤ 500	O(n3)