알고리즘 [파이썬] - 시간복잡도

🟦 시간복잡도

알고리즘에서 말하는 시간복잡도는 알고리즘 문제를 해결하기 위해 사용되는 연산의 횟수를 의미합니다.

파이썬 프로그램에서는 2,000만 번의 연산을 1초의 수행시간으로 예측합니다.

 

알고리즘 문제는 보통 시간 제한 안에 연산을 완료해 출력해야만 합니다. 따라서, 복잡한 알고리즘을 사용해 너무 많은 시간을 사용하면 안 되겠죠. 제한 시간 안에 해결할 수 있도록 적절한 알고리즘을 사용해야만 합니다. 

 

적절한 알고리즘 찾기

그렇다면 적절한 알고리즘이라는 것은 무엇일까요? 

 

이미 그 방법이 정립되어 시간복잡도가 계산된 알고리즘들이 있습니다. 시간 복잡도는 1, logn, n, nlogn, n^2, 2^n, n!과 같은 값을 갖습니다. 1에서 n!으로 갈수록 복잡도가 높은, 좋지 못한 알고리즘 입니다. 좋지 못한 알고리즘은 데이터의 크기가 커질 수록 연산 횟수가 증가하는 폭이 비교적 크게 상승합니다.

 

예를 들어, n의 최댓값이 1,000,000 (백 만)일 때 시간 복잡도 1인 알고리즘을 사용하면 1번의 연산만을 하게 됩니다. 시간 복잡도가 n인 알고리즘을 사용하면, 1,000,000 (백 만)의 연산을 하게됩니다. n^2인 알고리즘을 사용하면 1,000,000,000,000 (10조)의 연산이 발생하겠죠.

1	1
n	1,000,000
n^2	1,000,000,000,000

 

그러니, 시간복잡도를 보고 적절한 알고리즘을 선택해야 합니다.

 

시간 복잡도의 세 가지 표기법

시간 복잡도를 표현하는 세 가지의 표기법이 있습니다.

 

1. 빅-오메가 : 최선일 때의 연산 횟수를 나타내는 표기법

2. 빅-세타 : 보통일 때의 연산 횟수를 나타내는 표기법

3. 빅-오 : 최악일 때의 연산 횟수를 나타내는 표기법

 

알고리즘 문제를 푸는 데 신경써야 할 것은 빅-오 표기법으로 표현된 시간 복잡도입니다. 가장 최악일 때의 연산 횟수를 고려해야 연산을 완료하는 최악의 시간을 계산할 수 있습니다. 

 

모든 입력 데이터에 대해 시간 제한을 통과해야하기 때문에, 빅-오 표기법으로 표현된 시간 복잡도를 알고 있는 것이 중요합니다.

빅-오 표기법은 O(...)와 같은 형태로 표현합니다.

 

O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!) 와 같이 표현할 수 있겠죠?

 

시간 복잡도 예시

정렬 알고리즘을 예를 들어보겠습니다.

	시간 복잡도 (최악)
버블	O(n^2)
선택	O(n^2)
삽입	O(n^2)
퀵	O(n^2)
병합	O(nlogn)
기수	O(n)

 

가장 빠른 알고리즘을 찾는다면 기수 정렬 방법을 선택하는 것이 좋을 것입니다.

 

⭐파이썬에서 많이 사용되는 sort()함수의 시간복잡도는 nlogn입니다.

 

log값은 밑이 2인 log로 계산하면 됩니다.

 

시간 복잡도 도출하기

이미 알려진 알고리즘의 시간 복잡도를 외우는 것도 중요하지만, 자신이 짠 로직의 시간복잡도를 계산할 수 있어야 합니다. 그 방법은 다음과 같습니다.

 

1. 가장 큰 영향을 주는 연산 횟수 측정 

가장 많이 중첩된 반복문의 연산 횟수를 분석합니다.

 

2. 상수 무시

상수는 무시합니다.

 

예를 들어 다음과 같은 코드의 시간복잡도는 n^2입니다. 빅-오 표기법으로는 O(n^2)와 같이 나타냅니다.

for i in range(n):
	for j in range(n):
		print(i)

 

이런 시간 복잡도 도출 방법을 생각해본다면, 최대한 중첩된 반복문을 줄여야 효율적이라는 것을 쉽게 이해할 수 있을 것입니다.

 

+ 슈도 코드 (Pseudo-code) ; 의사코드

코드를 작성하기 전에 그 논리를 비프로그래밍 언어로 작성하는 코드를 의미합니다.

실제 프로그래밍 언어를 사용한 코드보다 직관적으로 이해하기 쉽습니다.

 

알고리즘의 대략적인 모델링이기 때문에 넓은 관점에서 로직을 검토해 볼 수 있습니다.