1. Big O
- 선형검색의 경우, 자료의 수만큼 절차수가 증가
- Input의 size가 N이면, O(N) 이렇게 표현하는게 Big O
- 시간복잡도를 빠르게 설명가능
- 알고리즘분석을 빠르게 분석할 수 있고, 언제 무엇을 쓸지 빠르게 파악 가능
- Big O는 상수를 크게 신경쓰지 않음.
2. O(1)
const print_array = (arr) => console.log(print(arr[0]));
print_array([1,2,3,4]);
- input의 크기랑 상관없이 1번만(Constant Time) 출력 하기에 O(1)로 포현.
- Graph
3. O(N)
const print_array = (arr) => {
for(let n in arr) {
console.log(n);
}
});
print_array([1,2,3,4]);
- 배열의 요소의 수만큼 스텝이 증가 하기에
- 선형구조의 경우 이러함
4. O(N2)
const print_array = (arr) => {
for(let n in arr) {
for(let x in n) {
console.log(x);
}
}
});
print_array([1,2,3,4]);
- Quadratic Time(2중배열)
- input이 10개면 100번의 스탭이 필요하듯
5. O(logN)
- Logarithumic Time(로그 시간)
- 이진검색의 경우
참고: 개발자라면 이제는 알아야하는...(노마드코더)