자료구조 - 시간복잡도 , Big-O(2022.09.18)

1. 시간복잡도

---

알고리즘의 수행시간은 최악의 입력에 대한 기본 연산 횟수로 정의한다. 사실 모든 입력에 대해 기본연산 횟수를 더한 후 평균을 낸 값이 정확한 값이지만 이는 현실적으로 불가능하므로 가장 안 좋은 입력에 대한 기본 연산 횟수를 측정하여 정의한다.

 

시간복잡도에 대한 예제로 아래 상황을 생각해보자.

 

1) 최댓값 구하기

algorithm arrayMax(A,n)
currentMax = A[0]

for i = 1 to n-1 do
	if CurrentMax < A[i]
    currentMax = A[i]
    
 return currentMax

arrayMax의 W.C.I (Worst Case Input)은 어떤 걸까? 

가장 최악의 상황은 for구문의 모든 값에 대해 if 구문이 참이어서 currnetMax의 값에 A[i]를 다시 삽입시키는 상황일 것이다. 따라서 A의 숫자들이 오름차순으로 정렬되어 있을 때라고 생각할 수 있다.

 

따라서 총 수행되는 횟수를 세어보면 

- 맨 처음 currentMax에 A[0]을 입력= 1번

- 각 값에 따라 currentMax값과 비교 = n-1번

- 각 값에 따라 currentMax값에 새로운 값 입력 = n-1 

 

따라서 총 2n-1번의 시행이 이루어지고 이를 함수로 T(n) = 2n-1 과 같이 표기한다.

 

2) 짝수 더하기

 

Algorithm sum1(A,n)
sum = 0
	for i=0 to n-1 do
    	if A[i]%2 == 0:
        	sum+ = A[i]
            
 return sum

 

위 예제는 주어진 수 중 짝수만 더하는 것으로 WCI는 모든 수가 짝수인 상황일 것이다.

 

총 수행 횟수를 세어보면

sum=0 시행 1번

 

각 for 값에 대하여  - A[I] % 2 연산 1번 / 결과값이 0과 같은지 비교 1번 총 2번

                              - sum += A[i]  더하기 + 대입으로 총 2번

 

 

T(n) = 4n+1을 얻을 수 있다.

 

 

3) 곱하여 더하기

Algorithm Sum2(A,n)
sum=0
	for i=0 to n-1 do
    	for j=i to n-1 do
        	sum+= A[i] * A[j]
 return sum

 

위 예제의 수행 횟수를 세어보면 

 

sum =0 시행 1번

각 for 값에 대한 연산은 아래와 같이 표로 정리하여 세어볼 수 있다. 

 

따라서 T(n) = 3n(n+1)/2  +1 이다.

 

2. BIG O 표기법

---

시간복잡도 함수의 최고차항만으로 간단하기 표기하는 방법

 

예를 들어 

T0(n) = 2n - 1은 n의 최고차항이 1차이므로 n으로만 표기한다. 이 때 O를 기호로 사용하여 O(n)과 같이 표기한다.

이때 -1과 같은 계수는 생략한다.

 

T1(n) = 4n-2 과 T0(n) = 2n -1은 정확히 T1이 T0의 2배이지만 Big O표기법으로 표기하면 둘다 O(n)으로 같다.

이는 증가율의 관점에서 보면 대수적으로 크게 문제되지 않는다.

 

 

 

1) 예제1

 

def increment-one(a): 
  return a+1

T(n) = 1 이므로 O(1)이다.

 

2) 예제2

def number-of-bits(n):
	count = 0
    while n>0
    	n=n//2
        count+=1
  return count

위 예제는 예를들어 n=8이 입력될 경우, while 구문을 통해 count = 3이된다. 

 

n이 1이 될 때까지 구문을 반복하므로 

위 식과 같은 과정을 통해 

 

O(logn)의 시간복잡도를 갖게 된다.(수식 입력의 한계로 입력하지 못하였으나 해당 로그의 밑은 2이다.)

 

 

 

---

 

본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.

 

자료구조 과목 소개 - YouTube