알고리즘 : 시간 복잡도 계산 빅오 표기법(BIG-O notation)

요약

• Big-O 표기법은 시간 복잡도(=시간 효율성) 와 공간 복잡도(=메모리 효율성) 을 나타낼 때 사용

• 데이터가 증가함에 따른 처리되는 시간의 증가율을 예측하기 위해 사용
  => 따라서 상수 무시, 가장 큰 영향력이 있는 항만 사용
  => ex) O(2n) 또는 O(n+1) 을 O(n) 으로 표시

• 실행시간 순서 빠른 ~ 느린 순서
  => O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)

복잡도에 따른 시간 그래프

=> 데이터가 증가(x축)에 따라 가파르게 상승(y축)할 수록 복잡도 증가

 

각 Big-O 표기별 설명

- O(1) => 단순 한번 입력에 결과 도출

def f(n) :
    return n+1

f(5)

 

-  O(logn) => 한번 검색할때마다 절반씩 검색할께 사라짐 => binary search (이진 탐색 트리 생각)

아래와 같이 Binary search tree 는 한 step 별 데이터 절반씩 제외 됨

출처: https://blog.penjee.com/wp-content/uploads/2015/11/binary-search-tree-sorted-array-animation.gif

 

- O(n) => n 만큼 반복됨 => 간단히 for 문 생각

n=5
for i in range(n):
    print(i)

 

-  O(nlogn) => 간단히 데이터를 나눠서 각 부분 집합의 순서를 맞추는 정렬의 경우를 생각

• QuickSort or mergeSort

아래는 mergeSort example

출처 : https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/618px-Merge_sort_algorithm_diagram.svg.png

 

- O(n^2) => n 의 제곱 만큼 반복됨 => 간단히 이중 for 문 생각

n = 5
for i in range(n):
    for j in range(n):
        print(i, j)

 

- O(2^n) => 하나의 데이터를 위해 반복 마다 가지치기로 많은 재귀가 일어나는 경우에 주로 발생 => 피보나치 수열

def fibo(num): 
    if num < 2: 
        return num 
    else: 
        return fibo(num-1) + fibo(num-2)

fibo(6)

 

Big-O 계산 보다 더 중요한 것은 알고리즘의 목표에 따라 더욱 간단히 구현하는 것을 항상 고민

• 복잡도 단순화 example 2가지

ex1) 1 ~ 10 까지 더하는 경우

# => for 문 사용시 O(n)
ans = 0
for i in range(11):
    ans +=i
print(ans)

=> O(n)을 아래와 같이 개선 O(1) ! 

# 1부터의 합을 구하는 알려진 수학 공식인 (1+n)*n/2 를 사용하는 경우
# => O(1)
ans = 0
ans = (1+10)*10/2
print(int(ans))

 

ex2) 피보나치 의 경우 

def fibo(num): 
    if num < 2: 
        return num 
    else: 
        return fibo(num-1) + fibo(num-2)

O(2^n) 을 아래와 같이 개선 O(n)

# 이보다는 아래와 같이 간단히 for 문으로도 가능
# => O(n) 으로 간단 해결
def fiboSimple(num):
    a, b = 0, 1
    for i in range(num):
        temp = b
        b = a + b
        a = temp
    return a

print(fiboSimple(10))