시간복잡도와 공간복잡도

알고리즘 성능 평가

- 시간 복잡도와 공간복잡도

동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 한다.

• 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 / 알고리즘을 실행하여 종료할 때까지 걸리는 시간
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 / 알고리즘을 실행하여 종료할 때까지 필요한 기억장치의 크기

 

1. 시간 복잡도

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.

같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라서 걸리는 시간이 달라지는데, 

같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스이다.

 

[시간 복잡도 그래프]

fasterO(1)<O(log n)<O(nlog n)<O(n²)<O(2ⁿ)slower
slower로 갈 수록 효율성이 떨어짐

 

[Big O]

시간 복잡도에는 빅-오 표기법의 개념이 등장한다. 

동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 

운이 안 좋다면 N번 만큼 동전을 튕겨야 하는 경우가 발생한다. 

이 최악의 경우를 계산하는 방식을 Big O 표기법이라고 부른다.

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다.

O(1)을 상수 시간이라고 부른다. n의 값은 얼마나 크던 상관 없다.

즉, 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다. 

ex) 배열에 있는 항목을 인덱스를 사용해 접근하는 경우

function constEx (arr) {
	console.log(arr[0])
}

 

O(log n)

입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘이다.

예로 데이터가 10배가 되면 처리 시간은 2배가 된다. 

ex) 2² 부터 n승까지 항목들을 출력 하는 경우

재귀가 순기능으로 이루어지는 경우도 해당된다.

2, 4, 8, 16, 32, 64

 

O(n)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다.

예로 데이터가 10배일 경우 처리 시간도 10배가 된다.

1차원인 for문이 대표적임

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

 

O(n log n)

데이터가 많아질수록 처리시간이 로그만큼 더 늘어나는 알고리즘이다.

예로 데이터가 10배가 되면 처리 시간은 20배가 된다. 

정렬 알고리즘 중 병렬 정합, 퀵 정렬이 대표적이다. 

 

O(nⁿ)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다.

예로 데이터가 10배가 되면 처리 시간은 최대 100배가 된다.

m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다. 

 

O(2ⁿ)

데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다. 

대표적으로 피보나치 수열이 있고, 재귀가 역기능을 할 경우도 해당된다. 

 

 

[빅오 표기법 예제]

O(1): Push, Pop

 

 

[Algorithm] 시간 복잡도, 공간 복잡도

 

 

---

2. 공간 복잡도

알고리즘에서 사용하는 메모리의 양을 나타냄.

 

작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이다.

시간 복잡도의 경우 알고리즘을 잘못 구성하면 결과값이 나오지 않거나 느린 속도로 나오기때문에 최근에는

공간복잡도 < 시간복잡도를 더 우선시하며 프로그래밍을 한다. 

 

좋은 알고리즘을 비교할 땐 시간이 빠른 경우 공간을 많이 사용하고, 시간이 느린 경우 공간을 적게 쓰는 경우가 있다.

 

[공간 복잡도에 영향을 미치는 요소]

알수있는 점: 공간 복잡도에서는 input이 얼마나 큰지는 중요하지 않다. 

• 변수
• 자료구조(data structure)
• 함수 호출(function call)
• 할당(allocation)

function booo(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('booo!');
  }
}

booo([1,2,3,4,5]);

해당 함수는 변수 i를 0이라고 선언한 것 외에는 공간 복잡도에 영향을 미치는 부분이 없다. 

이 경우 공간 복잡도는  O(1) 이다. 

 

function arrayOfHiNTimes(n) {
  let hiArray = []; 
  for (let i = 0; i < n; i++) {
    hiArray[i]='hi';
  }
  return hiArray;
}

arrayOfHiNTimes(6); // O(n)

위 코드는 for문 내에서 6번 반복적으로 실행되면서 공간을 6번을 활용했다. 

이 경우 공간 복잡도는 O(n)이다. 

 

[자료구조] 시간복잡도 with JavaScript