- 알고리즘의 성능 → 시간,공간 복잡도를 수학적 표현
- 알고리즘의 실제 러닝타임 표시 X → data나 사용자의 증가율에 따른 알고리즘의 성능 예측이 목표 → 상수는 1이 됨
O(1)
입력데이터의 크기에 상관없이 언제나 일정한 시간이 걸림
배열은 시작 주소 + 인덱스를 이용해 바로 위치를 계산할 수 있음
-> 메모리에 연속적으로 저장되기 때문
O(n)
입력데이터의 크기에 비례해 처리시간이 소요
n이 늘어날때마다 처리시간이 더 필요해짐
같은 비율로 데이터와 시간이 증가
O(n^2)
n을 돌리면서 n으로 루프 또 돌림
데이터가 커질수록 처리시간 부담도 더 커짐
O(nm)
O(n^2)과 비슷하지만, m이 n보다 작을 수도 있기때문에 엄연히 다른 복잡도.
m을 n만큼 또 돌림
O(n^3)
n을 삼중으로 돌림.
O(n^2)과 비슷한 양상을 보이지만 데이터가 증가함에 따라 더 급격하게 처리시간 늘어남
O(2^n) ( m개씩 n번 늘어나는 알고리즘: O(m^n) )
– 피보나치 함수
:호출할때마다 바로 전, 바로 전전 숫자가 필요→ 매번 함수가 호출될 때마다 2번씩 함수가 또 호출 ⇒트리의 높이만큼 반복
O(n^2),O(n^3) 보다도 데이터의 증가에 따른 처리시간 현저히 늘어남.
O(log n)
– 이진 검색
배열의 중간값과 key값 비교
처리진행할 때마다 검색해야하는 데이터의 양 1/2
순차검색보다도 속도가 현저히 빠름
O(n) 보다도 적게들고 데이터 증가해도 성능이 크게 차이나지 않음.
O(sqrt(n))
상수는 버림.
n을 2번 돌리는 코드 → O(2n) ⇒ 상수 버림, O(n)
