[자료구조]Big-O 표기법

Big-O 표기법

수행시간을 의미하는 T(n)함수값을 결정하는 최고차항만으로 간단하게 표기하는방법

입력값에 대한 증가율을 표기하는것이다.(수행시간이 차이가 있더라도 증가율이 같다면 같은 표기를 한다.)

O(최고차항)

• 최고차항만 남긴다
• 최고차항 계수(상수)는 생략해준다
• Big-O(최고차항)으로 표기한다

상수연산만 하는 알고리즘이라면?

def func1(n):
    return n+1
    
def func2(n):
    n += 1
    n += 1
    n += 1
    return n

fun1 과 func2 의 T(n)은 각각 1 과 3이다 하지만 두개다 상수이기 때문에 빅오 표기법에서는 아래와 같이 표기한다

O(n**0) = O(1)

증가율이 줄어드는 log의 경우는 어떻게 될까?!

def func1(n):
    count = 0
    while n > 0:
        n = n //2
        count =+ 1
    return count

 

n을 8이라고 가정해보자

n              = 8
n/2            = 4
n / 2**2       = 2
n / 2**3       = 1
n / 2 ** count = 0

n = 2 ** count
log 2**b = count

T(n) = C * log2**n +1 = O(log2**n)