시간복잡도 Big-oh (big-o) notation 점근 표기법

알고리즘에 대해 공부하다보면, 처음부터 볼 수 있는 개념이 하나 있다. 그것은 바로 시간복잡도이다.

현재 글을 적는 시점에서도, 나도 가끔 가다가 빅오표기법의 계산을 잘못하여 효율성을 잘못 따질때가 있다.

오늘은 이 시간복잡도에 대해서 알아보고자 한다.

모든 동작에는, 시간과 메모리가 필요로 한다. 이 중 시간복잡도는 프로그램을 실행할 때 소요되는 시간을 계산하는것이다.

구문, 함수의 종류 등에 의해 다양한 공식을 띄게 되는데, 크게 아래의 사진과 같은 방식으로 분류된다.

O(1), O(logn), O(n), O(n!) 등과 같은 방식이 존재하며, 위의 방식 이외에 적힌 식에 따라 O(n^5) 등 다양한 파생된 결과가 출력될 수 있다. 

X축은 투입되는 자료의 갯수, Y축은 그 자료들을 투입한 프로그램의 수행시간을 나타내는 것이다. 그리고 이 방식은, 어떠한 프로그램이 구동될 때, 완료까지 걸릴 최악의 경우를 계산하는 방식이기에 "아무리 시간이 많이 소요되어도 이 시간 안에는 끝낼 수 있을 것" 이라는 의미가 내포되어있다.

 

먼저 O(1)의 경우를 알아보도록 하겠다.

O(1) [constant] 

///

def print_first(my_list):     print(my_list[0]) print_first([2,3]) print_first([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53])

///

이런 경우를 들어보자. 과연 입력되는 수가 출력까지의 작동시간에 영향을 미칠까? 전혀 아니다. 주어진 리스트의 가장 첫번째 수를 출력하는 이 구문은, 그 수가 얼마나 길건, 리스트에 얼마나 많은 수가 추가되어있건, 정해진 하나의 수만 출력하면 되기에 무조건 한번만에 찾아낸다.

따라서 항상 수행시간이 한번뿐인 O(1)이라고 부를 수 있다.

 

다음은  O(logn)이다.

O(logn) [logarithmic]

///

def print_powers_of_two(n):     i = 1     while i < n:         print(i)         i = i * 2   print_powers_of_two(6)

def print_powers_of_two(n):     i = n     while i > 1:         print(i)         i = i / 2 print_powers_of_two(6)

///

이 경우는 입력하는 자료의 크기가 커지면 커질수록 처리에 필요한 시간이 log만큼 짧아지는 알고리즘이다. 이진탐색의 방법이 대표적이며, 재귀함수가 순기능으로 작동되는 경우도 위의 방식에 해당된다.

 

다음으로는 O(n)이다.

O(n) [linear]

///

def print_each(my_list):     for i in range(len(my_list)):         print(my_list[i]) print_each([1,2,3,4,5])

def print_three_times(my_list):     for i in range(len(my_list)):         print(my_list[i])     for i in range(len(my_list)):         print(my_list[i])     for i in range(len(my_list)):         print(my_list[i]) print_three_times([1,2,3,4,5])

///

O(n)은 입력하는 데이터의 크기에 "비례"하여 처리에 필요한 시간이 증가하는 알고리즘이다. 데이터의 갯수가 10배, 100배가 된다면, 걸리는 시간도 10배, 100배가 된다. 위의 경우와 같이, 1차원적인 for 반목문이 이 경우에 해당한다.

 

다음은 O(n logn)이다.

O(n logn) [linear-logarithmic]

///

def print_powers_of_two_repeatedly(n):     for i in range(n):          j = 1         while j < n:              print(i, j)             j = j * 2 print_powers_of_two_repeatedly(6)

def print_powers_of_two_repeatedly(n):     i = 1     while i < n:          for j in range(n):             print(i, j)         i = i * 2 print_powers_of_two_repeatedly(6)

///

 

n과 logn이 섞인 구문으로, 대표적 예시로는 while 구문과 for 구문이 합쳐져 있는 식을 볼 수 있다. 물론 2번째 식과 같이, for과 while의 순서가 바뀐다고해도 전혀 문제가 되지 않는다.  log n에서는 데이터가 10배가 되면 , 처리시간은 2배가 되었는데, 이 알고리즘에서는 n과 logn 이 합쳐진 만큼, 데이터가 10배가 된다면 처리시간은 2*10이 되어 20배 증가한다.

 

 

다음은 O(n^2)이다

O(n^2) [quadratic]

///

def print_pairs(my_list):     for i in range(len(my_list)):         for j in range(len(my_list)):             print(my_list[i], my_list[j]) print_pairs([1,2,3,4,5])

///

위와 같이 for 구문이 2차원적으로 쓰인 경우이다. 제곱의 개념으로 들어가기에, 데이터가 10배가 된다면 수행시간은 100배가 된다. 

 

여기서 for 구문의 차원에 따라 O(n^x)에서의 x가 결정된다.

 

마지막으로는 O(2^n)이다.

O(2^n) [exponential]

///

def fibo(n):     if n==2 or n==1:         return 1     return fibo(n-1)+fibo(n-2) for i in range(1,11):     print(fibo(i))

///

 

데이터량이 많아질수록, 처리시간이 "기하급수적"으로 증가하는 알고리즘이다. 대표적으로는 위에 적은 것과 같은 피보나치수열이 있고, 재귀함수가 역기능을 수행하는 경우도 이에 해당한다.