시간 복잡도
시간 복잡도(time complexity)는 코드의 실행 시간이 어떤 요인으로 결정되는지 나타내는 시간과 입력 데이터의 함수 관계 입니다.
코딩테스트에서는 자신이 짠 코드와 시간 복잡도를 계산하여 문제에서 요구하는 입력을 제한시간 내에 해결할 수 있는지 파악해야 합니다.
빅오 표기법
코딩 테스트에서 효율성을 검사하는 데 사용하는 시간 복잡도는 빅오(Big-O)표기법을 사용합니다.
빅오 표기법은 최악의 경우에 걸리는 시간과 입력 간의 상관관계를 표기하며 입력 크기가 N이고 이에 비례하는 시간이 걸린다면 O(N)으로 표기합니다.
예제코드
private int search(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i;
}
}
return -1;
}이 코드는 평균적으로 배열 중간쯤에서 원소를 찾게 될 것 입니다.
하지만 최악의 경우에는 모든 원소를 순회한 후 원소를 찾게 됩니다.
전체 배열을 순회하므로 O(N) 시간 복잡도를 갖게 됩니다.
빅오 표기법 사용 이유
효율성을 묻는 문제는 문제 제한 사항에 명시되어 있는 조건을 극한으로 맞추는 입력 데이터를 사용해서 코드를 평가하기 때문에 빅오 표기법을 사용합니다.
알고리즘과 시간 복잡도 표
| 알고리즘 | 시간 복잡도 |
|---|---|
| 이진 탐색 | O(logN) |
| 선형 탐색 | O(N) |
| 정렬 | O(N logN) |
| 조합 | O(2N) |
| 순열 | O(N!) |
이와 별개로 특별한 로직 없이 실행되는 사칙연산과 같은 단순 연산의 시간 복잡도는 상수 시간이라고 하며 O(1)로 표기한다.
시간 복잡도 계산하기
시간 복잡도는 정확한 실행 시간을 계산하는 용도가 아니다.
실행 시간이 어떤 요인으로 결정되는지 나타내는 수식일 뿐이기 때문에 곱하거나 더해지는 상수 부분은 나태내지 않는다.
예를들어 길이가 N인 배열의 반만 사용하는 알고리즘이 있다고 가정해보자.
반복 횟수는 N/2고 빅오 표기법으로 바꾸면 O(N/2)로 나타낸다.
하지만 위에서 설명했듯 상수부분은 제외한다고 했으니 O(N)으로만 표기한다.
이와 비슷하게 길이가 N인 배열을 두 번 반복하는 경우 O(2N)이 아니라 O(N)으로 표기한다.
주의
만약 배열을 M번 반복해야 한다면 M은 무시하면 안 된다. 이 경우에는 길이 N인 배열을 M번 반복해야 하므로 O(NM)이 되며, 문제 조건에 따라 N뿐만 아니라 M의 최대값 또한 구해서 시간 복잡도에 대입해야 한다.
또 다른 경우는 길이 N짜리 배열을 순회하고 그 다음에 길이 M짜리 배열을 순회하는 것이다.
이 경우에는 N번 반복한 후 M번 반복하므로 O(N+M)으로 표기한다.
이때도 N과 M의 최댓값을 구하여 시간 복잡도에 대입해서 효율성을 판단해야 한다.
시간 복잡도를 줄이는 방법
시간 복잡도 수식에 가장 큰 입력을 대입하여 계산한 결과가 1억 이상이라면 풀이가 효율적이지 않은 것이다.
따라서 더욱 효율적인 풀이를 생각해서 시간 복잡도를 줄여야한다.
예를 들어 정렬된 배열 arr에서 특정 원소의 위치를 찾는 문제를 떠올려보자
배열의 모든 원소를 순회한다면 이는 O(N)의 시간 복잡도가 소요된다.
하지만 정렬되어 있다는 조건에 주목하면 이진 탐색을 적용할 수 있다는 것을 알 수 있다.
이진 탐색의 시간 복잡도는 O(logN)이므로 훨씬 효율적으로 탐색**할 수 있다.
또한 배열에서 중복을 제거한 원소들을 찾고 싶을 때 원소별로 배열 전체를 순회하면 O(N²)의 시간 복잡도가 소요된다.
이 때는 자료 구조 Set을 이용하면 O(N)으로 해결할 수 있다.
O(N²)과 O(N)은 N의 크기가 커질수록 효율성 차이가 크게 난다.
