알고리즘 복잡도

시간 복잡도 & 공간 복잡도

 

알고리즘의 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

 

최근에는 하드웨어 메모리 용량이 커졌기 때문에, 알고리즘 성능 측정에서는 시간 복잡도가 좀 더 우선시된다.

 

1. 시간 복잡도

• 알고리즘에 필요한 단계 수만 고려한다.
• 데이터가 증가할수록 단계 수가 어떻게 변하는지를 말해준다.

2. 공간복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양이다.
• 정적으로 선언된 변수, 재귀함수와 같이 동적으로 공간을 계속해서 필요로 하는 경우도 포함한다.

 

빅 오 표기법

• 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 등장했다.
• 절대적인 실행 시간과 필요한 자원 공간의 양을 파악하기란 어려우므로, 빅 오 표기법으로 알고리즘의 효율성을 정량화할 수 있다.
• 입력 크기 N에 따라 연산이 몇 번 실행되는지를 표기하는 것이다.

1. 빅 오 표기법의 : 특징

• 시간 복잡도에 미미한 영향을 주는 요소는 표기하지 않는다. (데이터가 무수히 커질수록 무의미한 요소이기 때문이다.)
  • 상수항 무시
  • 계수 무시
  • 최고차항만 표기
• 일반적으로 최악의 시나리오를 기준으로 말한다.
  • 최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 알면, 최악을 대비함과 동시에 알고리즘 선택에 중요한 영향을 미칠 수 있다.
  • 그러나 대부분의 경우 평균적인 시나리오가 발생하긴 한다.
• 서로 다른 분류에 속하는 두 알고리즘이라면 어떤 알고리즘을 써야 할지 대체로 알 수 있다.
  • 같은 분류에 속하는 두 알고리즘이라면 어떤 게 더 빠른지 알기 위해 추가적인 분석이 필요하다.

2. 빅 오 표기법 : 종류

상수 시간 O(1)

• 알고리즘에 필요한 단계 수가 항상 일정하다.
  e.g. 배열 끝에 삽입, 삭제 등

선형 시간 O(N)

• 데이터가 하나씩 추가될 때마다 알고리즘이 한 단계씩 더 걸린다.
• 데이터의 수(N)가 증가함에 따라 실행시간도 선형적으로 증가한다.
  e.g. 배열 순회하면서 검색 등

로그 시간 O(log N)

• 데이터가 두 배로 증가할 때마다 한 단계씩 늘어난다.
• 연산이 한 번 실행될 때마다 데이터의 크기가 절반으로 감소한다는 의미다.
  e.g. 이진 탐색 등
  (참고로 컴퓨터 과학에서 생략된 로그의 밑은 2이다.)

이차 시간 O(N²)

• 데이터가 N개일 때 N² 단계가 걸린다.
• 데이터가 증가하면 단계 수가 급격히 늘어나므로 비교적 비효율적인 알고리즘으로 간주된다.
  e.g. 버블 정렬, 선택 정렬, 삽입 정렬 등

선형 로그 시간 O(N log N)

• O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 상태를 의미한다.
  e.g. 퀵 정렬, 병합 정렬, 힙 정렬 등
• 퀵 정렬의 효율성이 O(N log N)인 이유
  • 데이터를 분할하는 횟수는 log N이므로 O(log N)이다.
  • 각 분할 단계에서 pivot과의 비교와 교환 횟수를 계산하면 O(N)이다.
    n + n/2 + n/4 + n/8 + ...
  • 최악의 시나리오(데이터가 오름차순 또는 내림차순으로 한쪽으로 쏠려서 불균형하게 분할되는 경우)에서는 O(N²)이 될 수 있다.

 

3. 빅 오 표기법 : 효율성 비교

O(1) < O(log N) < O(N) < O(N log N) < O(N²)

 

참고

⌜누구나 자료구조와 알고리즘⌟ - 제이 웬그로우

⌜면접을 위한 CS 전공지식노트⌟ - 주홍철