02 알고리즘의 효율 분석

---

 

01 시간 복잡도

시간 복잡도란?

알고리즘은 시간 복잡도를 보고 선정해야합니다.

여기서 시간 복잡도(Time Complexity)란,

알고리즘의 성능을 나타내는 지표로 입력값과 연산 수행 시간의 상관관계를 나타내는 척도 입니다.

시간 복잡도는 낮을수록 좋습니다.

 

알고리즘 수행 시간을 측정하는 방법

절대 시간 측정

프로그램을 작성한 후 프로그램을 실행하여 결과가 나올 때 까지 시간을 측정합니다.

이 방법은 환경에 따라 달라질 수 있어서 코딩 테스트에서는 활용하지 않습니다.

 

시간 복잡도 측정

알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타내고, 그 결과를 최선, 보통, 최악으로 나눕니다.

입력 크기를 N으로 나타내고, 이에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.

그리고 상한선을 활용하는 점근전 표기법 중 가장 많이 사용하는것이 빅오 표기법(big-O notation)입니다.

• 빅오 표기는 연산 횟수가 f(x)라고 할 떄 최고차항을 남기고 계수를 지워 O(...) 식으로 표기하면 됩니다.
• 예를 들어 f(x) = 2x^2 + 3x + 5면 O(x^2)과 같이 표현합니다.

 

시작 복잡도를 코딩 테스트에 활용하는 방법

코딩 테스트 문제에는 제한 시간이 표기되어 있으므로 어떤 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을 지 계산해볼수있습니다.

저번 포스팅에서도 말했지만 '초당 연산 횟수를 1억 번'을 기준으로 잡습니다.

책에서 말하기로는 코딩 테스트 문제에서 대부분 제한 시간을 여유있게 지정하기 때문에 '1,000 ~ 3,000만' 정도로 고려하면 된다고 합니다. 밑에는 N의 가용 범위 표입니다.

시간 복잡도	N의 가용 범위
O(N!)	10
O(2^n)	20 ~ 25
O(N^3)	200 ~ 300
O(N^2)	3,000 ~ 5,000
O(NlogN)	100만
O(N)	1,000 ~ 2,000만
O(logN)	10억

 

만약 입력 데이터가 2000개라면 N^2의 복잡도를 가진 이중 for문을 고려해 볼 수 있겠습니다.