시간 복잡도

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 파이썬 프로그램에서는 2000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다고 한다.

시간 복잡도 유형

• 빅-오메가: 최선일 때의 연산 횟수를 나타낸 표기법이다.
• 빅-세타: 보통일 때의 연산 횟수를 타내낸 표기법이다.
• 빅-오: 최악일 때의 연산 횟수를 타내낸 표기법이다.

아래 예제에서 빅-오메가의 시간 복잡도는 1번, 빅-세타의 시간복잡도는 N/2번, 빅-오의 시간 복잡도는 N번이다.

import random
findnum = random.randrange(1, 101)

for i in range(1, 101):
	if i == rindnum:
    	print(i)
        break

코딩 테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다. 코딩 테스트에서는 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.

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

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다. 아래는 시간 복잡도 도출 기준을 나타낸다.

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

아래 두 코드의 시간 복잡도는 각 각 n과 3n이지만 실제 시간 복잡도는 상수를 제외하여 계산하기 때문에 n으로 같다.

n = 1000000
cnt = 1

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

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

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 아래 코드에서는 이중 for문(n²)이 전체 코드의 시간 복잡도 기준이 된다.

n = 1000000
cnt = 1

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

참고 Do it! 알고리즘 코딩테스트 with Python