최근에 정보처리기사 필기를 준비하면서 정렬에 관한 문제가 나올 때마다 빠짐 없이 나오는 것이 있는데 바로 '시간 복잡도'이다. 필기 준비할 때는 답을 외우는 게 빠르기 때문에 지나쳤지만 최근에 정렬에 관한 알고리즘을 공부하면서 시간 복잡도에 대해 알아보고 싶어서 정리를 시작하게 됐다.
시간 복잡도란?
-> 문제를 해결하는데 걸리는 시간과 입력함수의 관계를 나타내는 것이다. 이름에서부터 그 의미가 느껴지지만 면접에서 물어볼 날이 생기지 않을까라는 기대를 가지고 사전적 정의를 써봤다. 좀 더 쉽게 말하면 문제 해결을 하는데 시간이 얼마나 걸려?를 나타난 것이라고 보면 된다.
시간이 오래걸리면 복잡하다는 것을 다 알다시피 시간 복잡도가 크면 느린 알고리즘이고 시간 복잡도가 작으면 빠른 알고리즘이다. 그리고 시간 복잡도를 나타내는데 점근 표기법을 사용하는데 점근 표기법에는 3가지가 있다.
- 오메가 표기법 (Big-Ω Notation) : 최상의 경우
- 세타 표기법 (Big-θ Notation) : 평균의 경우
- 빅오 표기법 (Big-O Notation) : 최악의 경우
이 중에서 우리는 가장 많이 사용하는 방식인 빅오 표기법에 대해 알아보겠다.
Big-O(빅-오 표기법)
-> 위에서 말한 것처럼 빅-오 표기법은 최악의 경우를 고려하고 가장 차수가 높은 것만 남겨놓고 비교한다. 차수가 높은 n이 처리할 데이터가 많을수록 그 차이가 크기 때문입니다. 빅오 표기법은 식을 단순화하는 것보다 "알고리즘을 수행시간에 따른 성능 기준을 나누기 쉽다"에 의미가 있다. 그래서 정확한 식을 모르더라도 "이 알고리즘의 성능은 여기 정도다"라고 판단할 수 있는 것이다.
위의 식에서 알 수 있듯이 가장 큰 차수를 제외한 나머지는 제외하고 비교를 하는데 그만큼 n의 단위가 시간 복잡도에서 가장 큰 영향을 미친다. 어떻게 달라지는지 아래 그림에서 확인해보자.
O(1) (상수형)
- 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘
- 해쉬 검색 알고리즘 등
O(n) (선형)
- 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘
- 1차원 for문, 선형 검색 등
O(n log n) (로그선형)
- 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘
- 이진 탐색, 이진 트리 검색 등
O(n^2) (제곱형)
- 데이터가 많아질수록 급수적으로 시간이 늘어나는 알고리즘
- 삽입정렬 , 선택정렬 등
O(2^n) (지수형)
- 데이터가 많아질수록 급수적으로 시간이 늘어나는 알고리즘
- 피보나치 수열 등
위 그림에서 O(n) 위로는 n이 증가하더라도 드라마틱한 차이를 느끼기는 어렵지만 그 밑으로 내려갈수록 드라마틱한 차이를 보여준다.
지금까지 코딩을 하면서 시간 복잡도를 고려할 일이 없었기 때문에 이렇게 중요하다는 것을 미처 알지 못했는데 이번에 글을 작성하면서 그 중요성을 느낀 것 같아 다행이고 앞으로 시간 복잡도를 생각하면서 코딩을 하면 도움이 되지 않을까 싶다.
정렬 알고리즘 비교
위 그림은 정렬 알고리즘의 시간 복잡도를 보여주고 있다. 추후에 정렬에 대한 공부를 해서 정리하도록 하겠다.
▼ 도움을 주신 분들
https://wikidocs.net/34790
https://palyoung.tistory.com/37
https://blog.chulgil.me/algorithm/
https://coding-factory.tistory.com/608
'문제풀이 > 알고리즘' 카테고리의 다른 글
Counting Sort (계수 정렬) (0) | 2022.03.24 |
---|