Big-O

• 알고리즘의 성능을 수학적으로 표현해주는 표기법
• 알고리즘의 실제 러닝 타임을 나타내는 것이 목적이 아닌 데이터, 사용자 증가율에 따른 알고리즘의 성능 예측이 목적
• Big-O에는 시간 복잡도, 공간 복잡도가 있다.

시간 복잡도?

알고리즘을 수행하는데 실행 시간이 아닌 연산 횟수를 숫자로 표기한 것

시간 복잡도 함수

연산의 횟수를 데이터의 수 n의 함수로 나타낸 것을 시간 복잡도 함수 라고 함

Big-O 표기법

시간 복잡도의 불필요한 연산을 제거하고 데이터 증가에 따른 처리 횟수를 간단하게 보여주기 위한 목적으로 시간 복잡도를 표기하는 방법
최악의 경우를 가정하고 시간의 효율성을 계산하기 때문에 처리할 데이터의 갯수는 충분히 많다고 가정한다.

특징

1. 상수항 무시
   데이터(n)의 크기에 따라 영향을 받기 때문에 상수항은 제외한다.
   O(2n), O(3n) => n
2. 영향력 없는 항 무시
   데이터(n)의 크기에 따라 영향을 받기 때문에 가장 영향력 있는 항을 제외하고 나머지는 무시한다.
   O(n^2 + n) => O(n^2)

O(1)

입력 데이터 크기에 상관없이 동일한 처리 시간이 걸리는 알고리즘

function add(n) {
	console.log(n + n);
}
// n의 크기에 상관없이 연산은 한번만 일어나므로 O(1)

O(log n)

• 예) 이진 검색
• 처리가 진행될 때마다 처리 시간이 절반씩 줄어드는 경우

O(n)

입력 데이터 크기에 비례해서 처리 횟수가 비례하는 알고리즘
n이 10이면 10번 !

for (let i = 0; i < n; i++) {
	console.log(i)
}

for (let i = 0; i < n; i++) {
	console.log(i)
}
for (let j = 0; j < n; j++) {
	console.log(j)
}

O(n^2)

• 초반엔 천천히 증가하나 데이터가 증가할수록 처리시간이 급격히 증가하는 알고리즘
• 예) 이중 반복문

for (let i = 0; i < n; i++) {
	for (let j = 0; j < n; j++) {
    	console.log(i, j);
    }
}

공간 복잡도?

• 사용하는 메모리의 양