BigO 표기법 (BigO Notation)

BigO 표기법은 알고리즘이 얼마나 빠른지 확인할 수 있는 수학적 표기법으로 데이터 입력값의 크기에 따라 알고리즘 실행 속도의 변화를 설명하는 방법이다.

• 시간 복잡도: 알고리즘을 수행하는데 걸리는 시간 => 소프트웨어 성능에 영향
• 공간 복잡도: 문제해결을 위해 필요한 메모리 저장 공간 => 하드웨어 성능에 영향

최근에는 하드웨어의 성능이 증가하면서 공간 복잡도보다 소프트웨어의 성능인 시간 복잡도가 더 중요하다. 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표시하며 상수는 무시한다.

예를 들어 입력값 n에 대해 4n²+3n+4 번만큼 계산을 하는 함수가 있다면 이 함수의 시간 복잡도는 최고 차항인 4n²만 고려한다. 이때 계수인 4는 무시하며 n²만 고려해 시간 복잡도는 O(n²)이 된다.

Classification	Description
상수(Constant) O(1)	입력값에 영향을 받지 않는 이상적인 방법. 최고의 알고리즘이라고 할 수 있음.
로그(Logarithmic) O(log N)	입력값이 증가하면 실행시간이 약간 느려짐. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않음. ex) 이진검색
입력값(Linear) O(N)	입력값이 증가하면 동일하게 실행 시간도 증가함. 정렬되지 않은 리스트에서 최댓값 혹은 최솟값을 찾는 경우가 이에 해당됨.
다항식 (Polynomial) O(N²)	입력값이 증가하면 더 빠른 속도로 실행시간이 증가함. 비효율적임
지수제곱(Exponential) O(2^n)	다항식보다 비효율적임.
팩토리얼(Factorial) O(n!)	제일 비효율적임(= 제일 느린 알고리즘). 비추천!!

+) Hello Coding 그림으로 개념을 이해하는 알고리즘 책에서 나온 빅오 실행 시간에 대한 간단한 예제인데 종이를 접어서 네모 칸을 만들 때 각 알고리즘마다 걸리는 시간을 정리한 그림이다. 시간이 얼마나 걸리는지도 나와있어서 위의 그래프보다 이해하기 쉬운 것 같아서 추가했다.