[Algorithm & Data Structure] Big O notation

// "Normad Coder의 알고리즘과 데이터 구조 강의" 듣는 중//

​

Big O notation(표기법)

​

• 알고리즘의 스피드를 표현하는 방식.
• 빠르다, 느리다, 초로 표현 x --> 완료까지 걸리는 절차(steps)의 수
• so, 적을 수록 좋음.

• 예, linear search는 순서대로 해서, 10개면 10step 필요.
• => input size = N --> N steps
• => 선형 검색의 시간 복잡도 = O(N)

​

1. Constant Time (상수 시간) => O(1)

Array =["kimchi1", "pizza2", ... ,"galbi100"];

def print_first(arr):
    print(arr[0]) //kimchi1

• 이 코드는 배열의 수가 10개든 100개든 무조건 1step임.
• 첫 번째 꺼만 가지고 오고 싶으니까.
• 인풋의 크기는 의미가 없음.
• Constant Time (상수 시간) = N이 얼마나 크든 상관없이 끝내는 데 동일한 숫자의 스텝이 필요함
• 즉, 위 함수의 시간 복잡도는 상수시간. --> O(1)

 

Array =["kimchi1", "pizza2", ... ,"galbi100"];

def print_first(arr):
    print(arr[0]) //kimchi1
    print(arr[0]) //kimchi1

• 만약에 2번 같은 것을 인출해도 O(1).
• O(2) x Big O는 그냥 러프하게 인풋 사이즈에 따른 시간복잡도를 보는 것일 뿐. 디테일에 관심 없음.
• 왜냐하면, 이 함수는 인풋 사이즈와 상관없이 정해진 숫자에 따라 작동하는 것이기 때문에.
• => Big O 는 상수 constant를 신경 x
• => 함수 실행에 200step이 걸려도 인풋 상관없이 항상 200이면 걍 O(1)임. O(200) X
• => Constant Time of Algorithm --> O(1)
• 선호되긴 하지만, 항상 이렇게.. 만들 수가 없음.

​

​

2. Linear Time (선형 시간) => O(N)

def print_all(arr):
    for n in arr:    
        print(n)

• 각 아이템을 다 프린트하는 함수.
• 배열이 10개면 10개, 100개면 100개임 --> step이 커짐. --> O(N)
• linear search랑 비슷

def print_all(arr):
    for n in arr:    
        print(n)
    for n in arr:    
        print(n)

 

• 2번 해도 O(2N) 아님. 상수는 버리고 걍 O(N)

• => ​핵심은 인풋이 증가하면 시간복잡도가 증가한다는 거지; 정적 일차함수 그래프

​

3. Qudratic Time (2차 시간) => O(n2)

• Qudratic Time (2차 시간) --> nested loop 중첩 반복 시 발생

def print_twice(arr):
    for n in arr:    
        for x in arr:    
            print(x, n)

 

 

• 이 함수는 각 아이템에 대해 루프를 반복해서 실행함.
• 그러면 시간 복잡도가 n^2
• 인풋이 10개면 100번해야 함.
• 즉 이차함수임. --> O(n2)
• 선형 시간 복잡도가 더 효율적임. --> 즉, 젤 ... 비효율적임

​​

4. logarithmic time(로그 시간) => O(log n)

• logarithmic time(로그 시간) --> 이진 검색 알고리즘 설명할 때 씀
• 바이너리는 인풋이 2배여도 쪼개니깐 1step만 증가함.
• 그래서 이건 로그 함수임 --> O(log n)
• exponent 지수 <-> loarithm 로그

 

• 이진 검색은 일단 반 나누고 시작하니깐, 2배로 커져도 스텝은 1개만 증가. 걍 1번더 나누면 되니깐.
• so, 그래서 로그 함수임. --> O(log n)
• Big O는 base를 쓰지 않음. 즉 log32 이고 2 사라짐. 디테일 무시해서 그런 듯.
• 리니어보다 빠르지만, 콘스탄트 보다 느림.
• 근데 trade off 있음. ---> 이진 검색은 정렬되지 않은 함수 사용이 불가함.

​

출처: Nomard Coder 영상 캡쳐

• 가장 선호되는 것은 상수 시간 > 로그 시간 > 선형 시간 > 이차 시간 뒤로 갈수록 복잡해짐.
• 더 다양한 것들이 있는데 이게 가장 기본임.