Dec.23.21

iissaacc·2021년 12월 23일
0

TIL

목록 보기
9/10

Prologue

Big O Notation에 대한 이야기를 할 거다. 이건 알고리즘이 얼마나 효율적인지 가늠하는 지표로 쓰인다. 일반적으로 worst case를 상정하고 계산하고 가장 큰 수가 정해지면 자잘한 수들은 생략한다. 예를 들어 알고리즘의 step이 3n2+5n3n^2+5n이라고 할 때 이 알고리즘의 big O notation은 O(n2)O(n^2)이다. 5n5n을 생략하는 이유는 nn이 선형적으로 증가할 때 3n23n^25n5n의 그래프를 그려보면 확 와닿는다.

3n23n^2의 증가량이 5n5n의 증가량을 훨씬 압도해서 의미가 없기 때문이다. 그러면 3n23n^2에서 3은 왜 생략하는지 궁금해질텐데 상수가 있으나 없으나 기울기가 달라질 뿐 어차피 n2n^2의 범주에 있어서 더이상 골치아프게 생각하지 말자는 의미가 들어있다. 여기에서 유의미한 증가량이라고 말하려면 지수가 달라져야 한다.

이런 이유로 크게 big O notation을 5가지로 나누고 있다.

O(logn)O(1)O(nlogn)O(n)O(n2)O(\log n)\quad O(1)\quad O(n\log n)\quad O(n)\quad O(n^2)

What I've learned

여기까지가 내가 알고 있던 big o notation이다. 이번에 다시 살펴보면서 새롭게 알게된 내용은 크게 세 가지다.

  1. Big O notation은 worst case뿐만 아니라 자료구조가 커질 때 알고리즘의 step은 얼마나 커지나를 가늠하기도 한다.

  2. 두 알고리즘의 big o notation이 같을 때는 자료구조의 크기가 N일 때를 가정해서 알고리즘이 가지는 전체 step수를 비교한다.

  3. 정규분포를 보면 데이터가 평균에 몰려있듯이 알고리즘이 best case와 worst case를 만날 확률은 그렇게 높지 않다.

    worst case는 당연하고 average case를 생각해야 한다.

Epilogue

loop statemenet만 잘 계산하면 되지 않나? 하고 생각했었다. 예를 들어 짝수만 출력하는 코드를 작성한다고 해보자.

def print_even_num1(limit=100):
    num = 0
    while num <= limit:
        if num % 2 == 0:
            print(num)
        num += 1
        
def print_even_num2(limit=100):
    num = 0
    while num <= limit:
        print(num)
        num += 2

이 두 코드는 O(n)O(n)으로 같은 big O notation을 가진다. 한 줄씩 뜯어보면 print_even_num1은 loop 한 번에 1번 비교, 1번 num증가, 0.5번 출력한다. print_even_num2는 loop 한 번에 1번 출력, 1번 num증가한다. 두 함수의 step을 계산해보면 print_even_num1은 250 step, print_even_num2는 100 step으로 print_even_num2가 2.5배 효율적이라는 점을 알 수 있다.

0개의 댓글