알고리즘 시간 복잡도 빅오 표기법

 

일반적으로 알고리즘의 시간 복잡도를 O()의 형태로 많이 표현하는데, 이를 빅오 표기법이라고 한다

표기법	설명	예시
O(1)	입력에 관계없이 하나의 단계만을 거친다
O(n)	입력값과 1:1의 관계를 가진다	for문
O(n²)	입력값의 제곱만큼 수행된다	이중 for문 삽입 정렬 쉘 정렬 선택 정렬 버블 정렬 퀵 정렬
O(n³)	입력값의 세제곱만큼 수행된다	삼중 for문
O(nlogn)