Big O Notation(빅오 표기법) #3

💡 **[Colt Steele](https://www.udemy.com/user/coltsteele/) 의 JavaScript Algorithms and Data Structures Masterclass의 강의를 참고하여 정리한 글입니다.**

3. Big O 시간 복잡도

2페이지를 통해 보았듯이 입력에 따라 알고리즘의 런타임이 어떻게 증가하는지에 대한 것이 바로 Big O이다.

즉 입력과 해당 입력에 따른 상대적인 시간 간의 관계이다.

다양한 기본적인 표기법이 존재한다.

1. 선형함수 f(n) = n
2. 지수함수 f(n) = n^2, f(n) = 2^n etc...
3. 상수함수 f(n) = 1
4. 이외의 다양한 함수

위의 그래프는 블로그를 탐색하며 빅오의 개념을 정리한 글을 찾아보다 찾게된 그래프이다.

빅오 표기법에서 주로 사용되는 표기법을 시간 복잡도의 성능을 비교하는 그래프로

상수함수가 가장 효율성이 좋고 지수함수가 효율성이 제일 떨어지는 것을 볼 수 있다.

빅오 표기법의 표기법들에 대한 알고리즘의 관련을 보면 다음과 같다.

1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2^n): 피보나치 수열

이를 통해서 대략 기본적인 알고리즘의 시간 효율성에 대해서는 생각해볼 수 있겠다 싶었다.

그럼 이어서 solution2의 addUpTo(n) 함수는 어떤 빅오 표현식에 해당될까?

//solution2
function addUpToN(n) {
    return n * (n + 1) / 2;
}

solution2의 함수는 항상 3개의 연산을 수행하여 n 의 입력과 관련없이 항상 고정적인 연산을 수행하므로 O(1) 에 해당하는 상수함수에 해당할 것이다.

solution1의 경우 for 문이 존재하여 n 의 값에 따라 증가한다. 우리는 이를 5n+2 로 정리했었다. 그렇다면 빅오 표기법은 O(5n+2) 로 정의할 수 있을까? 결론은 그렇지 않다.

이는 빅오 표기법의 단순화에서 살펴보자.

참고자료

<https://noahlogs.tistory.com/27>