Big-O

Big-O 표기법은 소프트웨어의 성능을 보편적으로 표기하는 방법이다.

Big-O 표기법은 알고리즘의 효율성을 나타낸다.

그중에서도 상한선을 기준으로 효율성을 표현하느 것이 특징이다.

최고차항만을 생각

최고차항의 계수 무시

O($1$) : stack, push, pop

O($logn$) : 이진트리

O($n$) : for문

O($nlogn$) : 퀵 정렬, 병합 정렬, 힙 정렬

O($n^2$) : 이중 for문, 삽입 정렬, 거품 정렬, 선택 정렬

O($2^n$) : 피보나치 수열