[TIL_알고리즘] 시간복잡도를 표현하는 빅오표기법

시간복잡도 

빅오표기법(Big O)

def sum_ex1(N):

    sum = 0

    for n in (1,N+1):

        sum += n

    return sum

 

print(sum_ex1(100))

print(sum_ex2(1000))

 

시간복잡도: O(n)

n이 변하는 것에 따라 반복도가 바뀐다

 

def sum_ex2(N):

    return N*(N+1) //2

 

시간복잡도:O(1)

한번의 동작으로 결과가 나옴(상수식)

 

def ex_30:

    print("hello!)

시간복잡도: O(1)

 

def ex_40(N):

    for n in N:

        for m in N:

             print(n,m)

시간복잡도: O(n2)

 

factorial(n):

    if (n=1) return 1

    return n*factorial(n-1)

시간복잡도: O(n)

재귀함수로 n만큼 반복한다.