[알고리즘] Time Complexity(시간 복잡도) 알아보기

Time Complexity(시간 복잡도)

입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 쉽게 말해서

주어진 문제를 해결하기 위한 연산 횟수를 말한다.

일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 

 

시간 복잡도 정의하기

 

시간 복잡도 유형

• 빅-오메가(-Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(θ(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)): 최악일 때(worst case)의 연산횟수를 나타낸 표기법

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?

코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. 실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다. 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단 하므로 시간 복잡도는 항상 최악일 때(worst case)를 염두에 둬야 한다. 

 

시간 복잡도 활용하기

 

예시)

백준 2750 수 정렬하기 /   시간제한 2초

 

입력) 1번째 줄에 수의 개수 N(1<= N <=1,000,00), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는

절대값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

 

출력) 1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다. 

입력 -> 1 5,5,2,3,4,1 출력-> 1,2,3,4,5

 

시간제한이 2초 이므로 이므로 이 조건을 만족하려면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다. 

따라서 문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지를 판단이 가능하다.

-> 연산횟수는 1초에 1억번 연산하는 것을 기준으로 생각

-> 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클때를 기준 

 

연산 횟수 계산 방법

연산횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

 

알고리즘 적합성 평가

버블 정렬 : (1,000,000)^2 = 1,000,000,000,000 > 200,000,000 -> 부적합 

병합 정렬 : 1,000,000log(1,000,000) = 약 2,000,0000 < 200,000,000 -> 적합

 

문제에서 주어진 시간 제한이 2초이므로 연산 횟수 2억 번 안에 원하는 답을 구해야 한다.

버블 정렬은 약 10억번의 연산 횟수가 필요하므로 부적합하다. 병합정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있기 때문에 문제를 풀기 적합한 알고리즘이라고 판단이 가능하다.