대부분의 사람들이 코딩테스트를 처음 접한다면, 시간 복잡도에 관한 이야기를 듣게 될 것입니다.
시간복잡도를 보고 있으면 괜히 어렵고, 한숨만 나오는 그 기분을 저도 알고 있습니다...
오늘 이 포스팅에서는 시간 복잡도의 개념과 계산 법에 대해 알아보고 앞으로 시간 복잡도에 대해서는 두려움이 없는 개발취준생이 되어보자구요! 가즈아!!
시간복잡도란 ?
" 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산의 횟수를 말합니다 "
일반적으로 이 횟수는 1억번의 연산을 1초로 두고 계산합니다.
시간 복잡도는 Big(O) 표기법을 사용합니다. 이 표기법은 최악의 연산횟수를 기준으로 표기하는 방법입니다.
간단한 예시를 들어보자면 100만개의 수를 정렬하고, 시간 제한이 1초인 알고리즘 문제가 있습니다. 우리는 버블 정렬과 병합 정렬을 떠올릴 수 있습니다. 병합 정렬의 경우 시간 복잡도가 N^2 이고 병합 정렬의 경우에는 nlogn 의 시간 복잡도를 가지게 됩니다. 이 경우에 병합 정렬일 경우에는 연산의 횟수가 1000000^2 의 제곱, 즉 1,000,000,000,000 회의 연산이 일어나게 되고, 문제의 시간 제한 1초, 1억번의 연산횟수를 가볍게 뛰어넘기 때문에 문제가 발생합니다. 하지만 nlogn 의 시간 복잡도를 가지고 있는 병합 정렬의 경우에는 약 20000000회의 연산횟수만 발생하기 때문에 충분히 적합한 시간복잡도를 가진 알고리즘이라고 할 수 있습니다.
또한, 시간 복잡도를 계산할 때에는 가장 큰 복잡도를 가진 for문이나 코드를 기준으로 계산하게 됩니다. 알고리즘 로직을 구현하면서 시간복잡도를 유의하면서 작성하는 습관을 가지면 좋을 것 같습니다.
다음 포스팅에서는 배열과 관련된 알고리즘에 대해서 포스팅 해보도록 하겠습니다.