TIL_200908(Time Complexity) Part 2

이 글은 Stack Overflow에서 James Oravec님께서 작성하신 글을 참조하여 정리한 글입니다.

---

빅오 표기법은 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타냄.

1. O(1)

O(1) 알고리즘 예시 1:

다음 알고리즘은 console.log를 한 번만 실행하기 때문에 시간복잡도가 O(1)이라고 할 수 있음.

console.log("hello");

O(1) 알고리즘 예시 2:

알고리즘 2는 입력값 n과는 상관없이 "hello"를 3번만 console.log() console 창에 출력함.
즉, n의 값이 증가한다고 하더라도, 알고리즘 2는 console.log() 를 3번만 실행한다는 것이며, 이 경우 또한 시간복잡도 O(1)라고 할 수 있음(3회 실행되기는 하지만 3은 Constant 값이라고 생각하면 됨)

console.log("hello");
console.log("hello");
console.log("hello");

3. O(log(n)) - Logarithmic Examples:

Log_2 알고리즘 예시 3:

알고리즘 3은 log_2(n)의 시간복잡도를 가짐(시간 복잡도는 log(n)라고 표기함).

for(let i = 1; i <= n; i = i * 2) {
  console.log("hello");
}

Log_3 알고리즘 예시 4:

알고리즘 4는 log_3(n)의 시간복잡도를 가짐(시간 복잡도는 log(n)라고 표기함).

for(let i = 1; i <= n; i = i * 3) {
  console.log("hello");
}

Log_1.02 알고리즘 예시 5:

알고리즘 5 또한 비록 i에 1.02라는 숫자를 곱하기는 하지만, 곱하는 값이 1보다 크다면 logarithmic algorithm이라고 할 수 있음을 대표적으로 보여주는 예시임.

for(let i = 1; i < n; i = i * 1.02) {
  console.log("hello");
}

4. O(n) - Linear Time 예시:

O(n) 알고리즘 예시 6:

console.log가 O(n)만큼 실행 되는 예시임.

for(let i = 0; i < n; i++) {
  console.log("hello");
}

O(n) 알고리즘 예시 7:

이 알고리즘의 경우 n/2만큼 "hello"를 console.log하겠지만, 이는 '1/2'가 constant라고 하고 알고리즘 7의 시간복잡도는 O(n)이라고 함

for(let i = 0; i < n; i = i + 2) {
  console.log("hello");
}

5. O(n*log(n)) - nlog(n) 예시:

알고리즘 8 예시

O(log(n))과 O(n)이 결합된 형태라고 보면 됨.

for(let i = 0; i < n; i++) {
  for(let j = 1; j < n; j = j * 2) {
    console.log("hello");
  }
}

알고리즘 9 예시

알고리즘 9 예시 또한 일부 "Variation"이 존재하지만, 이 값들은 전부 Constant라고 할 수 있고, 시간 복잡도는 O(n log(n))이라고 함.

for(let i = 0; i < n; i = i + 2) {
  for(let j = 1; j < n; j = j * 3) {
    console.log("hello");
  }
}

6. O(n^2) n squared 예시:

알고리즘 10

O(n^2)는 이중 루프라고 생각하면 됨.

for(let i = 0; i < n; i++) {
  for(let j = 0; j < n; j++) {
    console.log("hello");
  }
}

알고리즘 11

"Variation"이 존재하기는 하지만, 이 또한 constant라고 생각하면 되며, 이 경우도 시간 복잡도가 O(n^2)라고 함.

for(let i = 0; i < n; i++) {
  for(let j = 0; j < n; j = j + 2) {
    console.log("hello");
  }
}

7. O(n^3) - n^3 예시:

알고리즘 12

이중 For 문이 아닌, 3중 For 문의 예시로, 이 경우에는 시간 복잡도가 O(n^3)임.

for(let i = 0; i < n; i++) {
  for(let j = 0; j < n; j++) {
    for(let k = 0; k < n; k++) {
      console.log("hello");
    }
  }
}

알고리즘 13

알고리즘 13 예시 또한 Variation이 일부 존재하지만, 이 또한 Constant라고 생각하면 되며, 시간 복잡도는 O(n^3)이라고 할 수 있음.

for(let i = 0; i < n; i++) {
  for(let j = 0; j < n + 5; j = j + 2) {
    for(let k = 0; k < n; k = k + 3) {
      console.log("hello");
    }
  }
}

---

Data Structure의 Operation별 시간 복잡도를 참고 하고 싶다면 다음 링크를 클릭해서 참조해보세요 ^^