Big-O
빅오표기법
1. 표기법
알고리즘의 성능을 수학적으로 표현해주는 표기법이다.
알고리즘의 시간과 공간 복잡도를 표현할 수 있다.
알고리즘의 실제 러닝타임을 표시하는 것이라기보다는 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표
상수와 같은 숫자들은 모두 1로 간주된다.
2. O(1)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다.
예) 입력값에 상관없이 특정 수를 반환하는 알고리즘
3. O(n)
입력데이터의 크기에 비례하여 수행되는 알고리즘
예를 들면, 배열의 길이만큼 순회하는 로직
4. O(n^2)
n을 중복해서 돌리는 것
데이터가 커질수록 처리 시간의 부담도 늘어나게 된다.
5. O(nm)
n번 반복하면서 매번 m번 반복하는 구조
6. O(n^3)
7. O(2^n), O(m^n)
n^3보다도 많은 시간복잡도를 자랑한다.
대표적인 예 : 피보나치
8. O(logn)
한번 연산할 때마다 연산해야할 데이터가 절반씩 줄어드는 알고리즘의 시간복잡도
대표적인 예) binary search
시간이 지날수록, 데이터가 늘어날수록 속도에 큰 변화가 없다.
9. O(sqrt(n))
10. 기억할 것! 상수는 과감히 버린다
증가하지 않는 숫자는 신경쓰지 않겠다.
Last updated
