[Algorithm]시간복잡도

시간복잡도란?

시간복잡도란 알고리즘의 성능을 설명하기 위해 사용하는 것이다.

연산을 몇 번 수행하는가?를 식으로 나타낸 것이다.

여기서 드는 의문은 시간복잡도인데 왜 시간이 아니라 왜 연산 횟수로 판단하지?? 

-> 컴퓨터의 하드웨어나 어떤 언어를 사용하는지에 따라 달라지기 때문에 연산 횟수만 고려하는 것

 

빅오 표기법(Big-O)?

빅오 표기법은 시간복잡도를 나타내는데 사용하는 점근적 표기법이다.

점근적 표기법에는 최상의 경우를 나타내는 오메가 표기법, 평균의 경우를 나타내는 세타 표기법, 최악의 경우를 나타내는 빅오 표기법이 있다.

이 중 빅오 표기법을 사용하는 이유는 최악의 경우에 걸리는 시간을 계산하여 이 알고리즘을 사용했을 때의 성능을 보장할 수 있기 때문이다.

(최악의 경우인데도 이 정도밖에 안걸린다!라고 자랑하는 느낌)

 

시간 복잡도 표기

O(1)

입력 크기 n이 증가하더라도 연산 횟수가 증가하지 않는다.

let arr = [1, 2, 3, 4, 5, 6];
let O_1_algorithm = () => {
  console.log(arr[0]);
};

O_1_algorithm();

입력크기 n과 상관없이 한 번의 연산만 수행한다.

 

O(logn)

입력 크기 n이 커질 때, 연산 횟수가 logn에 비례해서 증가한다.

let arr = [1, 2, 3, 4, 5, 6];
let O_logn_algorithm = () => {
  for (let i = 1; i <= arr.length; i *= 2) {
    console.log(arr[i]);
  }
};

O_logn_algorithm();

위의 코드는 3번 실행된다.

 

O(n)

입력 크기 n이 증가 함에 따라 같은 비율로 연산 횟수가 증가한다.

let arr = [1, 2, 3, 4, 5, 6];
let O_n_algorithm = () => {
  for(let i = 0; i < arr.length; i++) {
  	console.log(arr[i]);
  }
};

O_n_algorithm();

위의 코드는 6번 실행된다.

 

O(n^2)

입력 크기 n이 증가 함에 따라 연산 횟수가 n^2에 비례해서 증가한다.

let arr = [1, 2, 3, 4, 5, 6];
let O_logn2_algorithm = () => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i]);
    }
  }
};

O_logn2_algorithm();

위의 코드는 6*6인 36번 실행된다.

 

위의 사진은 입력값에 따른 시간복잡도를 나타낸 그림이다.

 

공간복잡도란?

공간복잡도란 알고리즘을 수행하기 위해 필요한 메모리 양을 나타내기 위해 사용하는 것이다.

요즘은 컴퓨터 성능이 많이 발전해서 메모리 공간이 많기 때문에 공간복잡도의 중요도는 떨어졌다고 한다.

시간복잡도가 오래걸리면 아예 결과값이 나오지 않거나 너무 느리게 나오기 때문에 시간복잡도에 더 중요도를 둔다.

---

코딩테스트 준비를 하면서 효율성에서 막혔던 경험이 많다.

내가 짠 코드의 대부분은 for문을 이용한 반복문이 많았는데,

이중 반복문이 들어가면 시간이 O(n^2)으로 걸리기 때문에 효율이 좋지 않았다.

어떻게 하면 시간복잡도가 적은 알고리즘으로 문제를 풀 수 있을지 고민하면서 코딩테스트 준비를 해야겠다.