빅오 표기법에 대해서 정말 자세하고, 잘 정리한 분들이 많다. 그래도 내가 보고 이해한 만큼만 정리해 보겠다.
Big O 표기법
: 알고리즘의 성능을 수학적으로 표현하는 표기법이다. 이를 통해서 시간과 공간의 복잡도를 표현할 수 있다. 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는것이 목표이다.
우선, Big O 표기법에 3가지 정도가 있다.
-
Big O(빅 오)
: 가장 많이 사용하고 있는방법이다. 그 이유는 빅 오가 가지고 있는 성격때문이다. 빅오는 다른 2개와 다르게, 최대 경우의 수 ?를 시간과 공간복잡도로 나타낼 수 있다. 즉 n 개의 데이터가 나열해 있는경우, 우리는 n개의 데이터를 순회하여, 원하는 데이터를 찾아야하기 때문이다. 다시 말해서, 최악의(마지막) 경우를 생각해야하기 때문에 빅 오를 많이 사용하고 있다. -
Big Ω (빅 오메가)
: 빅오와 상반되는 개념이다. -
Big Θ(빅 세타)
: 세타는 빅 오(O)와 빅 오메가(Ω) 사이에 존재한다.(평균)
Big O 표기법의 대표적인 예
1) O(1)
: 입렵 데이터에 상관없이 일정한 시간이 걸리는 알고리즘이다. 가장 적은 시간과 공간을 차지한다.
예) 배열 (ex) assign, push, pop
2) O(log n)
: 한번 처리가 진행될때마다, 검색해야하는 데이터양이 반으로 줄어드는 알고리즘을 나타낸다.
예) 이진 트리 자료구조
3) O(n)
: 입력 데이터 크기에 비례해서 처리하는 알고리즘을 말한다. 데이터와 시간이 비례적으로 증가한다.
예) Linked List
4) O(n^2)
: 가로n 세로 n 만큼 배열을 갖는 알고리즘을 처리할때 사용되어진다.
예) matrix형 (테이블), 이중 배열
5) O(n^3)
: n^2의 데이터 크기가 n만큼 더 가지고 있는 자료구조를 나타낼때 사용되는 알고리즘.
예) 큐브형
2) O(2^n)
: 피보나치
위의 예시를 그래프로 나타낼 수 있다.
위의 그래프에서 볼 수 있듯이, O(1)이 가장 효율적으로 빠르게 데이터를 찾을 수 있고, O(2^n)이 가장 비효율적이라고 말 할 수 있다.
(가장 효율적)O(1) < O(log n) < O(n) < O(n^2) < O(n^3) < O(2^n) < O(n!) (가장 비효율)
Big O표기법의 주의점
상수항을 사용하지 않는다.
: 데이터를 처리할때, 예를 들어 n(n+1)만큼의 걸리지만 빅 오로 나타낼때는 O(n^2)로, 또 2n 을 O(n)으로 표기한다.
