알고리즘 - 복잡도

알고리즘 초보자로서

처음 맞닥뜨릴 때 가장 당황하게 되는 용어는

'복잡도'인 것 같습니다.

 

오늘은 이 복잡도가 무엇인지 알아보도록 하겠습니다.

 

 

 

복잡도

---

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

 

복잡도의 종류는 다음과 같습니다.

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

쉽게 말해,

시간 복잡도는 문제를 해결하는 데 걸리는 '시간'을 의미하고,

공간 복잡도는 문제를 해결하는 데 필요한 '크기'를 의미합니다.

 

다시 정리하면 다음과 같습니다.

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

시간 복잡도와 공간 복잡도는 대체적으로 반비례 관계에 있습니다.

이러한 관계를 거래 관계(Trade-Off)라고 말합니다.

 

 

 

시간 복잡도

---

알고리즘 문제를 풀 때 표현되는 '복잡도'는

대게 시간 복잡도를 의미합니다.

 

시간 복잡도를 '알고리즘을 위해 필요한 연산의 횟수'로

'알고리즘을 위해 필요한 실행 시간'이 아닙니다.

 

실행시간으로 시간 복잡도를 고려하지 않는 것은

같은 알고리즘이라도 개인이나 기업이 가진

하드웨어 등에 의해 알고리즘 성능이 달라질 수 있기 때문입니다.

 

 

 

알고리즘 성능 평가

---

알고리즘의 성능 평가의 종류는 다음과 같습니다.

• 최선의 경우(Best Case) : 최선의 상황에서 작업 완료시까지 가장 빠른 시간을 산출
• 최악의 경우(Worst Case) : 최악의 상황에서 작업 완료시까지 가장 느린 시간을 산출
• 평균의 경우(Average Case) : 여러 상황에서 '총 실행시간 / 시행 횟수'를 산출

 

알고리즘 성능 평가시 주로 최악/평균 성능을 사용합니다.

알고리즘의 복잡도가 증대되면 평균 성능 평가가 어려워

최악 성능을 사용합니다.

 

 

 

빅오 표기법(Big-O)

---

일반적인 알고리즘에서 시간 복잡도를 표현할 때는

빅오 표기법을 주로 사용합니다.

 

빅오 표기법을 쉽게 표현하자면,

가장 빠르게 증가하는 항만을 고려하는 표기법 입니다.

 

빅오 표기법은 함수의 상한만을 나타낸다는 의미인데,

여기서 상한이란 알고리즘의 시간적 상한을 의미합니다.

 

예를 들어, 운전을 하여 약속 장소까지 향하는 중에

친구에게 전화를 받아 도착 예정 시간을 질문받았을 때,

본인이 판단하기에 아무리 늦어도 30분안에 도착할 것 같다고

판단하여 늦어도 30분 안에 도착한다고 말한다면,

약속 시간의 상한은 30분인 것입니다.

 

빅오 표기법은 이러한 시간의 상한,

즉 가장 늦는 경우의 수를 고려하는 표기법이기 때문에

알고리즘 성능 평가 중 '최악의 경우'를 평가하는 표기법입니다. 

 

다음은 자주 사용되는 빅오 표기법에 관한 표입니다.

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

 

이러한 빅오 표기법을 그림으로 나타내면 다음과 같습니다.

빅오 표기법

출처

 

 

 

빅오 표기법 고려 방법

---

빅오 표기법을 고려하는 방법은 다음과 같습니다.

• 계수와 낮은 차수의 항은 고려하지 않는다.
• 상수는 고려하지 않는다.

 

따라서 연산 횟수가 '3N³ + 5N² + 1,000,000'인 알고리즘에서

빅오 표기법에 따라서 복잡도를 표현하면 O(N³)으로 표기합니다.

 

하지만 이때 주의해야 할 것이 있습니다.

빅오 표기법에서 계수와 낮은 차수의 항 그리고 상수는 고려하지 않는데,

N값이 작다면 위의 식 '3N³ + 5N² + 1,000,000'에서

상수인 1,000,000이 끼치는 영향이 더 커지게 됩니다.

 

따라서 모든 경우에 빅오 표기법이 정확한 것은 아니라는 것을 인지해야 합니다.

 

 

 

빅오 표기법 예

---

• O(1) : 입력 자료의 수(N)와 관계 없이 복잡도가 동일하게 유지됩니다. 
  • 배열의 N번째 요소에 접근
  • 스택에 PUSH/POP
  • 해시 테이블의 원소에 접근
• O(logN) :  복잡도가 입력 자료의 수(N) 로그에 비례합니다.
  • 알고리즘의 각 단계에서 입력의 상당 부분(절반)을 실행하지 않습니다.
  • 이진 탐색 알고리즘(binary search)
• O(N) : 복잡도가 입력 자료의 수(N)에 정비례합니다.
  • 연결 리스트 순회
  • 최소/최대값 찾기
• O(NlogN) : 복잡도가 입력 자료의 수(N)와 입력 자료의 수(N) 로그 곱에 비례합니다.
  • 병합 정렬(merge sort)
  • 퀵 정렬(quick sort)
  • 힙 정렬(heap sort)
• O(N²) : 복잡도가 입력 자료의 수(N) 제곱에 비례합니다.
  • 버블 정렬(bubble sort)
  • 선택 정렬(selectrion sort)
  • 삽입 정렬(insertion sort)

 

 

자료구조와 빅오 표기법

---

자료구조에 따른 빅오 표기법은 다음 그림과 같습니다.

 

자료 구조에 따른 빅오 표기법

출처