시간복잡도 표기법 알아보기
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
일반적으로는 수행 시간은 1억 번의 연산을 1초로 간주하여 예측한다.
시간복잡도 정의하기
실제 시간 복잡도를 정의하는 3가지 유형은 다음과 같습니다.
시간 복잡도 유형
- 빅-오메가(big-Ω): 최선일 때(best case)의 연산 횟수를 나타낸 표기법
- 빅세타(big-Θ): 보통일 때(average case)의 연산 횟수를 나타낸 표기법
- 빅오(Big-O): 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
코딩테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?
코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산합니다.
실제 테스트 진행시에는 한개의 테스트만 성공하면 합격하는게 아닌 다양한 시나리오에 성공해야 합격이 됩니다. 그러므로 시간 복잡도를 판단할 때는 최악일 때를 염두해야 됩니다.
시간 복잡도 활용하기
문제의 시간제한이 2초이므로 1초에 1억번 즉 2억번 이내의 연산 횟수로 연산 문제를 풀어야 된다.
연산 횟수 계산 방법
- 연산 횟수 = 알고리즘 시간 복잡도 * 데이터 크기
위 공식을 대입하여 각 알고리즘이 이 문제에 맞는지 판단
알고리즘 적합성 평가
- 버블 정렬 = (1,000,000)² = 1,000,000,000,000 > 200,000,000 -> 부적합 알고리즘
- 병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 -> 적합
문제에 주어진 시간 제한이 2초이므로 연산 횟수 2억 번 안에 원하는 답을 구해야 됩니다.
버블 정렬은 약 10억 번의 연산 횟수가 필요하므로 이 문제를 풀기에 적합한 알고리즘이 아니라고 판단할 수 있다.
병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 적합한 알고리즘이라고 판단할 수 있다.
이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다.
즉 데이터의 크기(N)를 단서로 사용해야하는 알고리즘을 추측해볼 수 있다.
