[알고리즘] 알고리즘 선택의 기준이 되는 시간 복잡도

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃

https://youtu.be/DYA2q0oX5CA?si=jHYk_9XMkehcbeIm

---

코딩 테스트의 핵심 중 하나는 주어진 시간 내에 문제를 해결하는 것

이를 위해선 시간 복잡도를 고려해야 한다.

 

파이썬은 일반적으로 초당 2,000만 번 ~ 1억 번의 연산을 수행한다.

 

시간 복잡도 유형

• 빅-오메가(Ω(n)): 최선일 때의 연산 횟수를 나타낸 표기법
• 빅-세타(θ(n)): 평균일 때의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)): 최악일 때의 연산 횟수를 나타낸 표기법

 

코딩 테스트에선 최악인 경우를 기준으로 시간 복잡도를 계산하는 것이 좋다.

시간 복잡도는 데이터의 크기(N)에 따라 성능이 달라진다. 

최악인 시간 복잡도(빅-오) & 가장 큰 데이터 &초당 2,000만 번의 수행 시간으로 계산하자.

 

---

예를 들어, 2초 내에 N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하자.
N은 1 ~ 1,000,000의 범위를 갖는다.
버블 정렬 O(n^2)과 병합 정렬 O(nlogn) 중 적합한 알고리즘은 무엇일까?

우선, 시간 제한이 2초이므로 4천만번(2천만*2) 내에 결과를 얻어야 한다.

가장 큰 데이터 경우는 1,000,000이다.

 

버블 정렬의 경우, 시간 복잡도는 O(n^2)이므로 1,000,000 ^ 2 의 횟수가 필요하다. 4천만번이 넘는다.

병합 정렬의 경우, 시간 복잡도는 O(nlogn)이므로 1,000,000*log1,000,000 의 횟수가 필요하다. 4천만번이 넘지 않는다.

 

그러므로 버블 정렬의 경우는 적합하지 않은 알고리즘이다.

---

시간 복잡도에서 상수는 제외되며, 가장 많이 중첩된 반복문의 수행 횟수가 기준이 된다.

 

예를 들어, O(n)의 시간 복잡도를 갖는 for문이 3번 반복되면 n의 시간 복잡도를 갖는다.

아래 두 예제는 같은 시간 복잡도 N을 갖는다.

# 연산 횟수 = N

N = 1000000
cnt = 1

for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1

# 연산 횟수 = 3N

N = 1000000
cnt = 1

for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1
    
for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1
    
for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1

 

예를 들어, O(n)의 시간 복잡도를 갖는 for문 안에 O(n)의 시간 복잡도를 갖는 for문이 중첩되어 있다면 O(n^2)의 시간 복잡도를 갖는다.

# 연산 횟수 = N^2

N = 1000000
cnt = 1

for i in range(N):
	for j in range(N):
		print("연산 횟수 " + str(cnt))
    	cnt += 1