알고리즘의 시간복잡도(Time Complexity) / Big-O 표기법

Time Complexity

---

• 수행시간이란 특정 입력에 대해 수행되는 알고리즘의 기본연산(primitive operation)의 횟수를 말한다. (가상컴퓨터에서 가상언어로 작성된 가상코드를 실행한다고 가정
• 알고리즘의 수행시간 = 최악의 경우의 입력(worst-case input)에 대한 기본연산의 수행 횟수
• 입력의 크기 n에 대한 함수 T(n)으로 표기 -> 어떠한 입력에 대해서도 T(n) 시간 이내에 종료됨을 보장
  
  

▶ example

#input : n개의 정수가 담긴 배열 A
#output : A의 수 중에서 최대값
def func(A, n):
    max = 0  # 1번(할당)
    for i in A: 
        if i > max:  # n-1번(크기를 확인하는 최악의 경우)
            max = i  # n-1번(할당을 하는 최악의 경우)
    return max
            
 # T(n) = 2n - 1

 

Big-O Notation

---

• 정확한 횟수가 아니라 함수 값의 증가율이 가장 큰 항 하나로 수행시간을 간략히 표기하는 방법을 근사적 표기법(Asymptotic Notation)이라고 부르고, Big-O(대문자 O)로 표현한다.
• 수행시간의 증가 정도(rate of the growth of T(n) as n goes big)를 중시
• 최고차 항만을 남기고 나머지는 생략하는 식으로 수행시간을 간략히 표기한다.

 

▶ 표현 방법

 

• n이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략
• 가장 빨리 증가하는 항에 곱해진 상수 역시 생략
• 남은 항을 O() 안에 넣어 표기
  
  

▶ O(1) 시간 알고리즘 (constant time algorithm)

def add(a):
    return a+1

▶ O(log n) 시간 알고리즘(logarithmic time algorithm)

def get_bits(a):
    cnt =0
    while a > 0:
        a = a//2
        cnt+=1
    return cnt

▶ O(n) 시간 알고리즘(linear time algorithm)

def func(A, n):
    max = 0  
    for i in A: 
        if i > max:  
            max = i 
    return max

 

▶ O(n^2 ) 시간 알고리즘(quadratic time algorithm)

def list_sum(X, Y, n):
    sum=0
    for i in X:
        for j in Y:
            sum += i*j
    return sum

▶O(n^3 ) 시간 알고리즘(cubic time algorithm)

 

▶ O(2^n ) 이상의 시간이 필요한 알고리즘(exponential time algorithm)

 

 

 

사진 출처 :  https://www.bigocheatsheet.com/