알고리즘 복잡도

 

알고리즘 복잡도에 대해서 정리해보았습니다.

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

 

시간 복잡도 & 공간 복잡도

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

 

시간 복잡도

• 시간 단위가 아닌, 알고리즘에 필요한 단계 수만을 고려합니다.
• 데이터가 증가할수록 단계 수가 어떻게 변하는지를 말해줍니다.

 

공간 복잡도

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

 

빅 오 표기법

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

 

빅 오 표기법 특징

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

 

상수 시간 O(1)

• 데이터가 많든 적든 상관없이 알고리즘에 필요한 단계 수가 항상 일정합니다.
• e.g. 배열 끝에 삽입, 삭제 등

 

선형 시간 O(N)

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

 

로그 시간 O(log N)

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

 

이차 시간 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) 입니다.
  • 각 분할 단계에서 피봇과의 비교와 교환 횟수를 계산하면 O(N) 입니다.
    • n + n/2 + n/4 + n/8 + ...
  • 따라서 O(N log N)이 됩니다.
  • 최악의 시나리오(데이터가 오름차순 또는 내림차순으로 한쪽으로 쏠려서 불균형하게 분할되는 경우)에서는 O(N²)이 됩니다.

 

효율성 비교

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

 

참고

• 누구나 자료 구조와 알고리즘 - 제이 웬그로우
• 면접을 위한 CS 전공지식 노트 - 주홍철