1-3. Big-O 표기법

1. 시간 복잡도 분석

시간 복잡도의 개념에 대한 이해가 있어야 이번 게시글을 보기 편하다.

1. Big-O 표기법

점근적 상한

 Big-O 표기법(Big-O Notation)은 시간 복잡도와 공간 복잡도의 점근적 상한이다. Big-O 표기법에 대해서는 아래의 공식이 성립한다. 아래의 공식에서 n은 입력의 크기, f(n)은 알고리즘에서 실행되는 기본 연산의 횟수, g(n)은 기준 함수이다.

O(g(n)) = {f(n): there is positive constants c>0, n₀
s.t 0 <= f(n) <= c(g(n)) for n >= n₀

 

2. 알고리즘 분석 예시

1) O(1) 시간 알고리즘(Constant Time Algorithm): 입력 데이터에 상관 없이 언제나 일정한 처리 시간이 걸림.

   ex) 값을 1씩 증가시키는 함수, len(data),  배열에서의 인덱스 접근 data[i]

# 값을 1씩 증가시키는 함수

def increment_one(a):
	return a + 1

2) O(logn) 시간 알고리즘(Logarithmic Time Algorithm): 입력 데이터의 크기가 2배 증가할 때 처리 시간이 1씩 증가.

   ex) n을 이진수로 표현했을 때의 비트 수 계산(정수인 n을 반복적으로 2로 나누므로 O(logn)의 시간 복잡도)

def number_of_bits(n):
	count = 0
    while n > 0:
    	n = n // 2
   		count += 1
	return count

3) O(n) 알고리즘(Linear-Time Algorithm)

   ex) 크기가 n인 리스트에서 최댓값 구하기(전체 데이터를 한 번씩 확인하면서 max 값을 확인하므로 O(n))

def find_max(data):
	"""Return the maximum element from a nonempty Python List."""
    biggest = data[0]			# 초기화: O(1)
    for val in data:			# for문: O(n)
    	if val > biggest:		# if문: O(n)
        	biggest = val		# 큰 값으로 업데이트: O(logn)
    return biggest			# return: O(1)

 

3. 누적 평균 알고리즘

 누적 평균(Prefix Averages)은 크기가 n인 순열이 있을 때 처음부터 현재 요소까지의 평균을 구하는 알고리즘이다. 누적 평균에 대해서는 아래의 공식이 성립한다.

A[j] = ∑^j_i=0 S[j] / j + 1

 O(n^2) 시간 알고리즘은 매번 처음부터 현재까지 합산을 반복하는 방식으로, Nested loop로 되어 있어 O(n^2)의 시간 복잡도를 가진다. 두 번째의 경우에도 단순히 내장 함수 sum으로만 대체했으므로 시간 복잡도에 차이는 없다.

# O(n^2) 시간 알고리즘(Quadratic-Time Algorithm)

def prefix_average1(S):
	"""Return list such that, for all j, A[j] equals average of S[0],..., S[j]."""
    n = len(S)
    A = [0] * n
    for j in range(n):
    	total = 0
        for i in range(j+1):
        	total += S[i]
        A[j] = total / (j + 1)
    return A

# O(n^2) 시간 알고리즘(Quadratic-Time Algorithm)

def prefix_average2(S):
	"""Return list such that, for all j, A[j] equals average of S[0], ..., S[j]."""
    n = len(S)
    A = [0] * n						# create new list of n zeros
    for j in range:
    	A[j] = sum(S[0:j+1]) / (j+1)			#record the average
    return A

 O(n) 시간 알고리즘은 반복되는 합산 연산을 없앰으로써 O(n) 시간 복잡도를 갖게 되었다.

# O(n) 시간 알고리즘(Linear-Time Algorithm)

def prefix_average3(S):
	"""Return list such that, for all j, A[j] equals avaerage of S[0], ..., S[j]."""
    n = len(S)
    A = [0] * n					# create new list of zeros
    total = 0					# compute prefix sum as S[0] + S[1] + ...
    for j in range(n):		
    	total += S[j]				# update prefix sum to include S[j]
        A[j] = total / (j+1)			#compute average based on current sum
    return A

 

4. 세 종류의 집합 분리

 크기가 n인 순열 A, B, C가 있을 때 세 개의 교집합이 공집합인지 확인, 같은 요소가 있으면 disjoint하지 않은 것이다.

# O(n^3) 시간 알고리즘(Cubic Time Algorithm)

def disjoint1(A, B, C):
	"""Return True if there is no element common to all three lists."""
    for a in A:
    	for b in B:
        	for c in C:
            	if a == b == c:
                	return False			# we found a common value
                    
	return True

 3중 Nested loop는 O(n^3) 시간 복잡도를 가진다. 2중 Nested loop를 갖는 경우도 있다. 아래 코드를 참고하자.

def disjoint2(A, B, C):
	"""Return True if there is no element common to all three lists."""
    for a in A:
    	for b in B:
        	if a == b:			# only check C if we found match from A and B
            	for c in C:
                	if a == c:		# (and thus a == b == c)
                    	return False		# we found a common value
	return True				# if we reach this, sets are disjoint

 2중 Nested loop는 O(n^2)의 복잡도를 갖는다. 단 A와 B에서 a=b인 요소는 최대 n개만 존재하므로 C에 대한 for loop는 n번만 실행된다. C에 대한 loop는 O(n^2)의 시간 복잡도를 갖는다. 따라서 전체적 시간 복잡도는 O(n^2)이다.

 

5. 집합 중복 체크

 순열에 중복되는 요소가 있는지 확인하는 알고리즘이다. 2중 Nested loop는 O(n^2) 시간 복잡도를 갖는다.

def unique1(S):
	"""Return True if there are no duplicate elements in sequence S."""
    for j in range(len(S)):
    	for k in range(j+1, len(S)):
        	if S[j] == S[k]:
            	return False			# found duplicate pair
	return True				#if we reach this, elements were unique

 정렬 후 이웃하는 요소끼리 같은지 확인하며, 가장 빠른 알고리즘이 O(nlogn) 시간 알고리즘이다.

def unique2(S):
	"""Return True if there are no duplicate elements in sequence S."""
    temp = sorted(S)			#create a sorted copy of S
    for j in range(1, len(temp)):
    	if S[j-1] == S[j]:
        	return False		# found duplicate pair
	return True			# if we reach this, elements were unique

 

6. O(2^n) 시간 알고리즘

 O(2^n) 시간 알고리즘(Exponential Time Algorithm)이란 입력 데이터의 크기에 비례해 처리 시간이 지수적으로 늘어나는 알고리즘이다. O(2^n) 시간 알고리즘을 통하여 피보나치 수열의 시간 복잡도를 구해보자.

def fibonacci(k):
	if k <= 1: return k
    return fibonacci(k-1) + fibonacci(k-2)

다음 게시글에선 Big-O 표기법을 통해 여러 코드의 시간 복잡도를 구해볼 것이다.