[알고리즘]알고리즘의 복잡도와 설계 ti

알고리즘의 성능을 평가하는 지표는 크게 두 가지가 있습니다.

 

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간

공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량

 

당연히 복잡도가 낮을수록 좋은 알고리즘이 됩니다.

 

이중 for문이라던가 재귀함수라던가 문제를 굉장히 쉽게 풀 수 있음에도 어렵고 복잡한 알고리즘을

사용하는 이유는 이 복잡도를 줄기이 위해서입니다.

 

빅오 표기법(Big-O notation)

---

가장 차수가 높은 항만을 고려하는 표기법입니다. 다음의 예를 보겠습니다. 

 

$3N^3+ 5N^2+ 100000$

N의 3승의 차수가 가장 높으므로   $O(N^3)$이 됩니다. 

 

코딩 테스트에서는 일반적으로 $O(nlogn)$정도에서 해결을 목표로 합니다.

 

시간 복잡도에 대해서 예를 들어보겠습니다.

 

nums =[1,2,3,4,5,6,7]

while nums: 
	nums.pop()
    
if len(nums)==0:
	print("배열이 비었습니다")

 

배열에 들어있는 원소를 전부 비우는 알고리즘을 짠다고 생각해보겠습니다. 

리스트의 pop메소드를 통해서 구현하는 경우 배열의 길이만큼 시간 복잡도가 요구되기 때문에 

이 알고리즘의 경우 $O(N)$의 시간 복잡도를 가진다고 할 수 잇습니다. 

 

알고리즘 설계 Tip 

---

일반적으로 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억번을 넘어가는 경우 Python을 기준으로

5-15초 정도 걸린다고 합니다 

 

코팅 테스의 시간제한은 1-5초 가량이기 때문에 $O(N^2)$까지 가지 않도록 알고리즘을 설계하는 것이 굉장히 중요합니다 

물론 N의 범위가 작을 수록 더 복잡한 알고리즘을 사용해도 시간 범위 안에 문제를 풀 수 있습니다.

 

 

많은 사람들이 사용하고 있는 백준 온라인 저지를 기준으로 하면 위의 도표와 같습니다. 

데이터가 11보다 작은 경우에는 팩토리얼 정도의 시간복잡도를 사용하는 알고리즘의 경우에도 사용이 가능합니다

 

 

그렇기 때문에 문제를 해결하기 전에 어느 정도의 시간복잡도로 해결해야 하는지 파악하는 것이 중요합니다.