빅오(Big-O) 표기법

What is Big-O?

• 알고리즘의 성능을 수학적으로 표현해주는 표기법
• 시간과 공간 복잡도를 표현할 수 있음
• 데이터나 사용자의 증가에 따른 알고리즘의 성능을 측정하는 것이 목표
• 상수는 모두 1이 됨

 

O(1)

• 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘

 

O(n)

• 입력 데이터의 크기에 비례해서 처리 시간이 늘어나는 알고리즘

 

O(n^2)

• 입력 데이터의 크기만큼 각각의 요소에서 돌 때(ex. 이중 포문)

 

O(nm)

• m을 n만큼 돌릴 때(만약 m과 n이 같다면 O(n^2))

 

O(n^3)

• 입력 데이터의 크기만큼 세 번 돌 때(ex. 삼중 포문)

 

O(2^n)

• 재귀 함수로 구현 한 피보나치수열

 

O(logn)

• 한 번 처리할 때마다 검색해야 하는 데이터의 양이 절반으로 줄어드는 알고리즘(ex. 이진 검색)

 

O(sqrt(n))

• 데이터 사이즈의 제곱근만큼만 돌릴 때

 

참고

https://youtu.be/6Iq5iMCVsXA