Big-O 표기법

(계속 업데이트 중)

Big-O 표기법

• 알고리즘의 성능을 수학적으로 표현하는 표기법
• 알고리즘의 시간과 공간 복잡도 표현 가능
• 알고리즘의 러닝타임이 아닌 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표

O(1)

• 입력 데이터에 상관 없이 언제나 일정한 시간이 걸리는 알고리즘
• 데이터가 아무리 증가해도 성능이 똑같음

O(n)

• 데이터가 증가함에 따라 시간이 같은비율로 증가함
• 예시 : for문

O(n^2)

• 이중 for문은 시간복잡도가 n인 for가 두번 발생하므로 n * n = n^2이 된다

O(nm)

• 자칫하면 n^2과 착각 할 수 있지만 n과 m의 배열 수가 차이나게 다르다면 nm으로 표기해줌

O(n^3)

• 삼중 for문을 돌리는 경우

O(2^n)

• 예시 : 피보나치 수열 (재귀함수)
• 함수가 호출될 때 마다 2번씩 반복됨

O(m^n)

• m개식 n번 늘어나는 알고리즘

O(log n)

• 예시 : 이진검색
• 함수가 호출될 때 마다 데이터가 절반씩 줄어듦

O(sqrt(n))

• 제곱근 형식으로 데이터 찾아냄