Big O표기법은 알고리즘의 Time Complexity(시간 복잡도)를 나타내는데 주로 사용된다.
Time Complexity
데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 것
여기서 측정은 시간으로 하는 것이 아니라 얼마나 많은 단계(steps)가 많는지로 측정
Time Complexity 종류
O(1) Constant Time
입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸린다.
데이터가 증가함에 따라 성능의 차이가 없다.
ex) 인덱스가 0번인 값을 확인하고자할 때, 그 것만 확인한다.
const inputs = [1, 2, 3];
console.log(inputs[0]);O(n) Linear Time
입력 데이터의 크기와 비례해서 처리 시간이 걸리는 알고리즘을 표현할 때 사용.
항상 데이터와 시간이 비례해서 증가하기 때문에 그래프는 상승하는 직선으로 표현됨.
ex) 배열을 처음부터 하나씩 열어서 찾는 값을 확인한다. 배열의 길이가 10이거나 100이거나 길이에 상관없이
const inputs = [1, 2, 3];
for(let i = 0; i < inputs.length; i++) {
console.log(inputs[i]);
}O(n2) Quadratic Time
데이터 수의 제곱만큼 처리수가 늘어나는 때를 말함.
n개의 데이터를 받으면 각각의 엘리먼트에서 n번씩 또 돌기 때문에 데이터가 커지면 커질수록 처리시간의 부담이 커진다.(첫번 째 사진 참조)
const inputs = [1, 2, 3];
for(let i = 0; i < inputs.length; i++) {
for(let j = 0; j < inputs.length; j++) {
console.log(inputs[j])
}
}O(log n) Logarithmic Time
로그는 지수의 정반대로, 입력 데이터가 2배로 증가해도 실행 절차는 1씩만 커진다.
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
대표적인 알고리즘으로는 이진검색(Binary Search)이 있다.
이진검색은 한 줄로 정렬된 배열의 중간 값을 기준으로 선택하여, 기준 값과 key값을 크고 작음을 비교하는 방식이다.
but, 이진검색은 정렬되지 않은 배열에는 사용할 수 없다.
O(2n) Exponential Time
원하는 값을 찾으려면 몇 번을 나눠야 하는지 계산하는 방식
피보나치 수는 1부터 시작해서 한 면을 기준으로 정사각형을 만든다.
그리고 두개가 붙어 직사각형이 만들어지는데 큰을 기준으로 또 정사각형을 만든다.
피보나치 수는 황금 비율 등의 우리 주변을 둘러싼 수많은 자연 현상과 관련이 있다.
수열의 처음 두 숫자는 1이고, 그 다음 항목들은 2(1+1), 3(1+2), 5(2+3)가 된다.
