[코비] 5.1 복잡도

최정윤·2023년 10월 17일

코비

목록 보기

24/38

동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을수록 좋은 알고리즘이라고 한다.
복잡도는 알고리즘의 성능을 나타내는 척도다.
복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.
효율적인 알고리즘이란?
알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터내의 메모리와 같은 자원을 덜 사용하는 것이 효율적이라고 할 수 있다.

5.1.1 시간 복잡도(Time Complexity)

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

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

Big-O(빅 오)표기법

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

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

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

Big-O

O(1) - Constant Time

상수 시간
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않음
예) stack의 push, pop

O(log n) - Log Time

로그 시간
입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘
데이터 10배 → 처리 시간 2배
예) 재귀가 순기능으로 이루어질 경우, binary search 알고리즘, tree 형태의 자료구조 탐색

O(n) - Linear Time

선형 시간
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘
데이터 10배 → 처리 시간 10배
예) 1차원인 for문이 대표적

O(n log n) - Log linear Time

로그 선형 시간
데이터가 많아질수록 처리 시간이 로그만큼 더 늘어나는 알고리즘
데이터 10배 → 처리 시간 20배
예) 병합/퀵/힙 정렬

O(nⁿ) - Quadratic/Cubic Time

이차/삼차 시간
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘
데이터 10배 → 처리 시간 100배
예) 이중 for문, 삽입/거품/선택 정렬

O(2ⁿ) - exponential Time

지수 시간
데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘
예) 피보나치 수열, 재귀가 역기능할 경우

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

5.1.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);