Big O 표기법

Big O 표기법은 최악의 경우 알고리즘 수행 시간을 나타낸다.

 

아래 표는 효율적인 순서대로 작성했다.

Big O	형태	설명	추천 알고리즘
O(1)	상수 형태	해당 알고리즘이 일정한 상수 시간에 종료됨.	해시 테이블
O(log n)	로그 형태	입력값 n이 증가하는 속도보다 수행시간이 천천히 증가하는 알고리즘.	이진 탐색, 유클리드 호제법
O(n)	선형	입력값 n 만큼의 수행시간을 요구함.	순차 탐색
O(n log n)	선형로그 형태	선형 로그 형태로 수행시간이 필요함.	병합 정렬, 퀵 정렬, 힙 정렬
O(n ^ 2)	다차 형태	n에 대한 다차 형태로 수행시간이 증가함. for문이 중첩되어있는 만큼 지수가 증가함.	버블 정렬, 삽입 정렬, 선택 정렬 행렬 곱셉 ( O(n ^ 3) )
O(2 ^ n)	지수 형태	n이 지수인 형태로 수행시간이 증가함. 메모이제이션을 하지 않은 재귀함수가 이런 형태를 가진다.	조합 전체 탐색
O(n!)	팩토리얼 형태	n의 팩토리얼 형태로 수행시간을 요구하며, 이 이상의 시간복잡도는 억지로 만들지 않는 한 볼 수 없다.	순열 전체 탐색

 

시간 복잡도 비교 그래프 (출처 : https://m.hanbit.co.kr/media/channel/view.html?cms_code=CMS7965376216)