빅오표기법이란?

시간 복잡도를 표현하는 표기법으로써

시간 복잡도란 해당하는 알고리즘이 데이터 양에 따라서 처리하는 시간이 얼마나 걸리는지에 대한 표현이다.

1. O(1)

상수형 빅-오 , 데이터의 양과는 상관없이 일정한 실행 시간을 가진다

ex) 해쉬검색 알고리즘

2. O(log n)

로그형 빅-오, 데이터 양이 많아져도 증가율에 비해서 연산횟수의 증가율이 훨씬 낮다.

ex) divide&conquer(이진 검색, mergesort, quicksort)

3. O(n)

선형 빅-오, 데이터 양에 따라 시간이 정비례 한다.

ex) 선형탐색, 1중 for문

4. O(n*log n)

선형로그형 빅-오, 데이터양이 N배 많아지면 실행 시간은 N배 보다 조금더 많아 진다.(정비례 하지 않음)

ex) divide&conquer 이후에 다시 하나로 모으는 경우, 이진 트리 검색시 로직에 for문을 덮어 씌우는 경우

5. O(n²) (n의 제곱)

데이터 양에 따라 걸리는 시간은 제곱에 비례한다.

ex) 2중 for문, 삽입정렬, 선택정렬, 버블정렬

6. O(n³) (n의 세제곱)

데이터 양에 따라 걸리는 시간은 세제곱에 비례한다.

ex) 3중으로 중첩된 반복문

7. O(2ⁿ)

지수형 빅-오,  지수적 증가라는 무서운 연산횟수의 증가를 보임, 사용하는것 자체가 비현실적인 알고리즘

속도가 빠른 순서는 1번부터 ~ 7번 순서이다.