시간복잡도(BigO)

1. 시간복잡도

• 알고리즘의 수행시간은 기본연산의 수행횟수로 정의 된다.
• 수행횟수의 평균을 구하는 것이 쉽지 않으므로 알고리즘의 최악(가장 오래 걸리는)의 수행시간을 해당 알고리즘의 수행시간으로 측정한다.

-> 어떤 알고리즘의 시간복잡도 T(n)은 최악의 경우 입력에 대해 기본연산(비교, 복사, 산술, 논리, 논리비트)의 횟수

 

 예를 들면 길이가 n인 리스트 A에서 최대의 수를 구하는 알고리즘을 생각해보자. 선형탐색을 통해 최대의 수를 구한다면, 첫 수부터 n번째 수까지 차례로 수의 크기를 비교하게 될 것이다.

def arrayMax(A,n)
	currentMax = A[0] #1회
    	for i in range(1,n):
    		if currentMax < A[i] #비교 n-1
    			currentMax = A[i] #대입 n-1
		return currentMax

리스트 A가 오름차순으로 정렬되어 있어야 대입 연산이 가장 많게 된다. 따라서 해당 경우 시간 복잡도는 1 + (n-1) + (n-1)로 T(n) = 2n-1이 된다. 

2. Big-O 표기법

• 최악의 입력에 대한 기본연산의 횟수를 정확히 세는 것은 힘들다.
• n의 입력의 크기가 커질 때 수행시간 증가하는 정도가 훨씬 중요하다. 즉, 최고차항이 얼마나 큰가가 중요하다.
• 이러한 최고차항만 간편하게 표기하는 것이 Big-O 표기법이다. O(최고차항)

- O(1) 알고리즘 : 값을 1증가시킨 후 리턴. 상수 함수이다.

- O(logn) 알고리즘 : n을 이진수로 표현했을 때의 비트 수 계산 알고리즘이다.

- O(n) 알고리즘 : n개 수 중에서 최대값 찾는 알고리즘이다.

- O(n^2) 알고리즘 : 두 배열 A, B의 모든 정수 쌍의 곱의 합을 계산하는 알고리즘이다.

 

 코딩을 어떻게 하느냐에 따라 동일한 결과를 내는데 어떤 코드는 1초도 안되서 끝나는 반면 어떤 코드는 1분이 넘게 걸릴 수도 있다. 이러한 시간 복잡도는 프로그램의 성능에 중대한 영향을 미치고, 코테에서도 중요하게 생각하는 영역이기 때문에 항상 코드를 짤 때 신경 써서 해야한다. 다음은 같은 결과를 내지만 다른 시간 복잡도를 갖는 코드의 예시이다.

 

 Z 리스트에 대해 prefix sum S는 다음과 같이 정의된다.

S[i] = Z[0] + Z[1] + ... + Z[i]

ex) Z = [1,2,3,4] -> S = [1,3,6,10]

import time, random
a = int(input()) # n 입력받음
Z = []
S = []

for i in range(a): # 리스트 X를 randint를 호출하여 n개의 랜덤한 숫자로 채움
	x = random.randint(-999,999)
	Z.append(x)

def prefixSum1(X, n):
	for i in range(n):
		S.append(0) #S리스트에 자리 만들어주기
		for j in range(i+1):
			S[i] += X[j]

def prefixSum2(X, n):
	S.append(X[0])
	for i in range(1,n):
		S.append(0) #S리스트에 자리 만들어주기
		S[i] = S[i-1] + X[i] 
	# code for prefixSum2
	
random.seed()		# random 함수 초기화

before1 = time.process_time()
prefixSum1(Z, a) # prefixSum1 호출
after1 = time.process_time()
print(after1 - before1) # 두 함수의 수행시간 출력 

S = []
before2 = time.process_time()
prefixSum2(Z, a) # prefixSum1 호출
after2 = time.process_time()
print(after2 - before2) # 두 함수의 수행시간 출력

 위의 코드에서 prefixSum1은 X의 1~i번째 인덱스까지의 숫자를 다 더하고 그 값을 S[i]에 대입하는 방법이다. 반면에 prefixSum2는 S[i-1]의 숫자에 X[i]를 더한 수를 S[i]에 대입하는 방법이다. prefixSum1의 시간 복잡도는 for문이 두 번 돌기 때문에 O(n^2)이고, prefixSum2의 시간 복잡도는 for문이 한 번 돌기 때문에 O(n)이다. 이런 차이가 발생하는 이유는 prefixSum1에서는 했던 연산을 또 반복하기 때문이다. prefixSum2에서는 S(i-1)에서 해놓은 덧셈을 이용하고 거기에 한 번 더 연산하는 것이기 때문에 훨씬 효율적이다. 반드시 해야되는 연산은 생략할 수 없지만, 이미 해놓은 것을 이용하거나 쓸 데 없는 연산을 최대한 줄이는 것이 시간 복잡도를 최대한 줄이는 방법이다. 

 

 잘못된 내용 있으면 댓글로 알려주시면 감사하겠습니다~