[Python] 자료구조: 시간복잡도 Big - O 정리

<왜 알아야 할까>

같은 작업을 하는 코드여도 어떤 알고리즘을 사용했는지에 따라 실행 시간과 사용하는 메모리 공간이 달라진다. 실행 시간이 짧고 메모리 공간을 절약하는 코드가 효율적인 코드라 볼 수 있을 것이다. 1부터 n까지 더한 값을 return하는 코드들의 비교로 감을 잡아보자. 

 

def sum1(n):
    sum = 0
    for i in range(n):
    	sum += (i+1)
    return sum

 

위의 코드는 for문을 함수인자 n의 값만큼 실행한다. 1부터 100까지 더한다고 치면 100번 덧셈 연산을 수행한다.

 

def sum2(n):
    return (n+1)*n/2

 

위의 코드는 등차급수의 합(점화식) 공식을 이용한 코드인데 곱셈과 나누기를 한번씩 하고 바로 값을 return한다. n이 작다면 실행시간이 거의 차이나지 않는다. 만약 함수 인자 값 n이 100이 아니라 100만, 1000만 등의 큰 수로 가면 어떻게 될까? 시간을 측정하는 time module을 이용하여 실행시간을 비교해보자. 

 

import time

def sum1(n): 
    start = time.time() 
    ans = 0
    
    for i in range(1, n+1): 
        ans = ans + i
    end = time.time()
    
    print('실행시간:',end-start,'값:',ans)
    
def sum2(n):
    start = time.time()
    ans = n*(n+1)/2 
    end = time.time()
    print('실행시간:',end-start,'값:',ans)

 

sum1은 함수 인자 값이 커질수록 실행시간도 커지고 있음을 확인할 수 있다. sum2는 함수 인자 값의 크기에 상관없이 실행 시간이 매우 짧다. (실제로 0초인 것은 아니지만 time.time() 메소드는 매우 짧은 시간 간격은 0초로 보여준다.)

sum2가 실행시간이 짧으므로 이 코드를 쓰는게 시간적으로 더 효율적일 것이다. 이처럼 코드의 실행 시간을 줄이기 위해 내장 함수나 작성한 알고리즘의 시간복잡도를 알고 분석하는 것이 필요하다.

 

 

 

<개념>

 

함수 인자가 매우 클 때(또는 무한으로 갈 때)의 시간 복잡도를 표현하는 방법을 Big-O notation이라고 한다. 코드에서 수행하는 연산이나 작업의 수를 수량화한 것이다.

 

이때 함수의 인자의 크기를 n이라 하고 O(f(n)) 으로 나타낸다. f(n) (=괄호 안에 들어가는 식)은 1, n, logn, n^2, 등 n에 대한 단항식이고 계수는 고려하지 않는다. 계수는 고려하지 않고, n^2이 있으면 그보다 작은 차수인 n이나 logn은 고려하지 않는다. 따라서 Big-O 분석 시에 연산이나 작업의 수를 정확히 다 고려할 필요는 없다. 일반적으로 for문이나 while문같은 loop의 수가 Big-O에 결정적이다. 종류에 따른 이름은 다음과 같다.

 

 

f(n)	name
1	constant
log N	logarithmic
N	linear
N log N	superlinear
N^2	quadratic
N^c	polynomial
c^N	exponential
N!	factorial

 

 

출처: geeksforgeeks - Analysis of Algorithms Big-O analysis

 

 

위의 sum1은 for문 반복문이 n번 실행되고, 실행 시간도 n의 값과 비례하므로 O(n)이다. 반면 sum2는 점화식 계산 연산 한번만 수행하므로 O(1)에 해당한다. 다른 예시도 한번 살펴보자.

 

import numpy as np

def bigO(n):
    matrix = np,zeros((n,n))
    
    for i in range(n):
        for j in range(n)
            matrix[i][j] = i+j
    
    sigma = 0
    for i in range(n):
        sigma += (i+1)
    
    a = 1
    b = 2
    c = 3

 

 

중첩된 for문의 시간복잡도는 n^2 이고, 밑의 for문의 시간복잡도는 n이다. a,b,c 와 같은 할당문은 1에 해당한다. 따라서 이 함수의 시간복잡도는 O(n^2)으로 나타낼 수 있다.

 

 

<내장 함수 Big-O 정리>

 

List

Operation	Big - O
index / index assignment	O(1)
append	O(1)
pop(i)	O(n)
del	O(n)
contain (=in)	O(n)
del slice	O(n)
reverse	O(n)
sort	O(nlogn)
pop()	O(1)
insert(i,item)	O(n)
iteration	O(n)
get slice	O(k)
set slice	O(n+k)
concatenate	O(k)

 

Dictionary

Operation	Big-O
copy	O(n)
get item	O(1)
set item	O(1)
delete item	O(1)
contain (in)	O(1)
iteration	O(n)

 

+ list의 sort를 보면 nlogn으로 상당히 복잡도가 크다. 시간복잡도를 더 줄이기 위해 search 알고리즘이 필요한 이유기도 하다.