[0-1] 시간복잡도

 

* 이 게시글은 이지스 퍼블리싱의 <Do it! 알고리즘 코딩 테스트>를 기반으로 작성되었습니다.

 

시간 복잡도 : 주어진 문제를 해결하기 위한 연산 횟수.

 

 

시간 복잡도 정의하기

• 시간 복잡도를 정의하는 3가지 유형은 다음과 같다.
  • 빅-오메가 : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법
  • 빅-세타 : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법
  • 빅-오 : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법
• 1~100 사이의 무작위값을 찾아 출력하는 코드를 수행할 때,
  • 빅 오메가의 시간 복잡도 : 1
  • 빅 세타의 시간 복잡도 : 2/N
  • 빅-오의 시간 복잡도 : N

• 실제 코딩 테스트에서는 다양한 테스트 케이스를 수행하여 모든 케이스를 통과해야만 합격하기에 항상 최악일 때를 염두해야 한다. 즉, 빅-오(O(n)) 표기법을 사용해야 한다!

 

알고리즘 선택의 기준으로 시간 복잡도 사용하기

• 버블 정렬의 시간복잡도가 O(n^2), 병합 정렬의 시간 복잡도가 O(nlong)이라는 사실을 알고 있을 때, N개의 수를 정렬하는 코드를 작성하려면 어떤 정렬을 써야 할까? (1 <= N <=1,000,000) (시간 제한 2초)
  • 시간 제한이 2초이고, 파이썬은 연산 횟수를 1초에 2,000만 번 연산하는 것으로 생각하므로, 문제의 조건을 만족하려면 4,000만 번 이하의 연산 횟수로 이 문제를 해결해야 한다.
  • 우리는 최악의 경우를 생각하므로, 시간 복잡도 n 값에 데이터의 최대 크기를 대입하여 도출하면 된다.
  • 각 알고리즘의 적합성 평가
    • 버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 > 40,000,000 -> 부적합 알고리즘
    • 병합 정렬 = 1,000,0000log2(1,000,000) = 약 20,000,000 < 40,000,000 -> 적합 알고리즘
• 이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있다!

 

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

• 시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다.
• 코드에서 시간 복잡도 도출 기준
  • 상수는 시간 복잡도 계산에서 제외한다
  • 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

# ex1 : 연산 횟수 = N
N = 100
cnt = 1

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

# ex2 : 연산 횟수 = 3N
N = 100
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

• ex1과 ex2의 연산 횟수는 3배 차이가 나고, 이는 큰 차이인 것 같지만 상수를 무시하믈고 두 코드 모두 시간 복잡도는 O(n)이다.

# ex3 : 연산 횟수 = N^2
N = 100
cnt = 1

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

• 반면, 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 ex3에서는 이중 for문이 시간 복잡도 기준이 되고, 해당 코드의 시간 복잡도는 O(n^2)이 된다.
• 만약 ex3에 일반 반복문이 10개 더 있다 하더라도 시간 복잡도는 여전히 O(n^2)이다.