Big-0 표기법

Big-0란?

알고리즘의 성능을 수학적으로 표현해주는 표기법.
-> 시간과 공간복잡도 표현이 가능하다.
-> 데이터나 사용자의 증가율에 따른 알고리즘의 성능의 예측이 목표!!
-> 상수와 같은 숫자는 모두 과감하게 버려준다. ex)O(2n) => O(n)

Big-0 표기법

1. O(1)

-> 데이터의 크기에 상관 없이 언제나 일정한 시간이 걸리는 알고리즘이다.

->위의 그림과 같이 O(1)은 데이터가 증가함에 따라 성능의 변화가 없다.

2. O(n)

-> 입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘이다.

->데이터가 증가함에 따라 비례해서 처리시간도 같이 증가한다.

3. o(n²)

-> n을 돌리면서 그 안에서 n으로 루프를 또 돌릴때 n²이 된다.
-> 가로, 세로 길이로 가지는 면적만큼 처리횟수가 된다.

-> 데이터가 커짐에 따라 처리시간의 부담이 커진다.

4. O(n³)

-> Loop를 n으로 갖고 3중으로 돌리면 n³이 된다.

-> 위와 같이 큐빅의 모양을 띄게 된다.

-> O(n²)과 비슷하지만 데이터가 증가함에 따라 O(n²)보다 급격하게 처리시간이 증가한다.

5. O(nm)

-> m을 n만큼 진행하는 알고리즘이다.
-> O(n²)와 같은 그래프를 갖는다.

6. O(2ⁿ)

-> 대표적으로 피보나치 수열이 있다.

-> 앞서 본 표기법보다 데이터의 증가에 따라 더욱 가파르게 시간이 증가한다.

7. O(logn)

-> 대표적으로 Binary Search가 있다.
-> 한번 처리가 진행될 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘이다.

->데이터가 증가해도 성능의 차이는 크게 없다.