[Algorithm] 시간복잡도

해당 포스팅은  https://www.youtube.com/watch?v=DYA2q0oX5CA 강의자료를 참고하여 작성하였습니다. 

 

---

1. 시간 복잡도란?

• 주어진 문제를 해결하기 위한 연산 횟수를 말합니다.
• 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 생각합니다. 

---

2. 시간 복잡도 정의

빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기법 

빅-세타 : 보통일 때(average case)의 연산 횟수를 나타낸 표기법

빅-오 : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 

코딩 테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋습니다. 

---

3. 시간 복잡도 활용하기 

① 알고리즘 선택의 기준으로 사용 

 

e.g. 백준 온라인 저지 2750번 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

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

 

연산 횟수 계산 방법 
연산 횟수 = 알고리즘 시간 복잡도 n 값에 데이터의 최대크기를 대입하여 도출
위의 예시에서 데이터의 최대 크기는 1,000이다. 

 

 

알고리즘 적합성 평가 

버블 정렬 = (1,000) ^2  = 1,000,000 < 20,000,000 → 적합 알고리즘 

병합 정렬 = 1,000log_2(1,000) = 약 ~  < 20,000,000 → 적합 알고리즘 

 

두 정렬 모두 문제를 풀기에 적합한 알고리즘이라고 할 수 있지만, 병합 정렬이 더 효율적인 방법이라고 판단된다. 

 

② 시간 복잡도를 바탕으로 코드 로직 개선하기 

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

예제1. 연산 횟수 = N 

N = 1000 
cnt = 1 

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

 

예제2. 연산 횟수 = 3N

N = 1000
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

 

두 예제 코드는 연산 횟수가 3배가 차이 나지만, 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간복잡도는 O(n)으로 동일합니다. 

 

예제3. 연산횟수 = N^2

N = 1000 
cnt = 1

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

 

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 위의 코드에서는 이중 for문이 전체 코드의 시간 복잡도가 됩니다. 

 

이와 같이 자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있으며, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결 할 수 있습니다.