시간 복잡도와 공간 복잡도

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

복잡도는 알고리즘의 성능을 나타내는 척도다.

복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.

효율적인 알고리즘이란?

알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터내의 메모리와 같은 자원을 덜 사용하는 것이 효율적이라고 할 수 있다.

 

1. 시간 복잡도(Time Complexity)

시간 복잡도란 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석, 알고리즘을 실행하여 종료할 때까지 걸리는 시간을 의미한다.

즉, 알고리즘을 위해 필요한 연산의 횟수를 말한다.

 

Big-O(빅 오)표기법

시간 복잡도를 표기하는 방법 중에 가장 많이 사용하는 표기법은 Big-O(빅 오)표기법이다.

Big-O(빅 오)표기법은 알고리즘 최악의 실행 시간을 표기한다.

동전을 튕겨서 뒷면이 나올 확률을 이야기할 때, 운이 좋으면 한 번에 뒷면이 나오겠지만 운이 안 좋다면 N번만큼 동전을 튕겨야 할 수 있다. 이 최악의 경우를 계산하는 방식을 Big-O 표기법이라고 한다.

Big-O

1. O(1) - Constant Time
   • 상수 시간
   • 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
   • 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않음
   • 예) stack의 push, pop
2. O(log n) - Log Time
   • 로그 시간
   • 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘
   • 데이터 10배 → 처리 시간 2배
   • 예) 재귀가 순기능으로 이루어질 경우, binary search 알고리즘, tree 형태의 자료구조 탐색
3. O(n) - Linear Time
   • 선형 시간
   • 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘
   • 데이터 10배 → 처리 시간 10배
   • 예) 1차원인 for문이 대표적
4. O(n log n) - Log linear Time
   • 로그 선형 시간
   • 데이터가 많아질수록 처리 시간이 로그만큼 더 늘어나는 알고리즘
   • 데이터 10배 → 처리 시간 20배
   • 예) 병합/퀵/힙 정렬
5. O(nⁿ) - Quadratic/Cubic Time
   • 이차/삼차 시간
   • 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘
   • 데이터 10배 → 처리 시간 100배
   • 예) 이중 for문, 삽입/거품/선택 정렬
6. O(2ⁿ) - exponential Time
   • 지수 시간
   • 데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘
   • 예) 피보나치 수열, 재귀가 역기능할 경우

Big-O 표기법은 여러 경우에 대한 성능의 상한을 표기한 것이며,

Big-Ω 표기법은 하한을 표기한 것이다.

 

 

2. 공간 복잡도 (Space Complexity)

공간 복잡도란 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석, 알고리즘을 실행하여 종료할 때까지 필요한 기억장치의 크기를 의미한다.

즉, 알고리즘을 위해 필요한 메모리의 양을 말한다.

 

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

• 변수
• 자료 구조(Data structure)
• 함수 호출(Function call)
• 할당(Allocation)

 

공간 복잡도에도 동일하게 Big-O 표기법을 이용할 수 있다.

// O(1)
function Space1(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('Space Complexity!');
  }
}
Space1([1,2,3,4,5]);

// O(n)
function Space2(n) {
  let array = []; 
  for (let i = 0; i < n; i++) {
    array[i]='hi';
  }
  return array;
}
Space2(5);

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

두번째 함수는 for문 내에 5번 반복 실행되면서 공간을 5번 사용했다.

 

시간 복잡도(Time Complexity) vs 공간 복잡도(Space Complexity)

좋은 알고리즘은 시간이 적게 걸리고 자원의 사용도 적어야 한다.

하지만 시간과 공간은 반비례적인 경향이 있기 때문에

시간이 빠른 경우엔 공간을 많이 사용하고, 시간이 느린 경우 공간을 적게 쓰는 경우가 있다.

대부분 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.

 

---

참고

https://2mango.tistory.com/27

https://itprogramming119.tistory.com/entry/Javascript-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A0%95%EB%A6%AC-%EB%B0%8F-%EC%98%88%EC%A0%9C

https://velog.io/@nana-moon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95big-O-notation%EC%9D%B4%EB%9E%80

https://nohack.tistory.com/65