Section 2: Big O

Big O

코드의 성능을 평가하는 일반적인 지표로 사용되는 일종의 시스템

하나의 문제는 여러가지 풀이 방식이 존재하고 무엇이 가장 좋은가에 대한 물음을 수학적으로 표현해 지표를 제공할 수 있음

여러 접근법의 장단점을 파악하기 쉽고 디버깅 시 성능에 영향을 미치는 부분을 쉽게 파악할 수 있다.

면접에 자주 나오니 잘 알아두라고 함.

코드 시간 제기

1에서 특정 N 값 사이의 모든 숫자를 더하는 함수를 만드시오


function(3) // 1 + 2 + 3 = 6


function a(n){
	let total = 0;
	for (let i = 1; i <= n; i++){
		total += i;
	}
	return total;
}

function b(n){
	return n * (n + 1) /2;
}

어느게 더 좋은지의 의미는?

빠른가?

메모리를 덜 사용하는가?

더 가독성이 좋은가?

여기서 빠르기는 어떻게 측정하나?

JS의 내장 함수 performance.now() 사용하기


function a(n){
	let total = 0;
	for (let i = 1; i <= n; i++){
		total += i;
	}
	return total;
}

let t1 = performance.now();
a(100000000000);
let t2 = performance.now();
console.log(`time ${(t2 - t1 / 1000}`)

10억으로 위 두 함수를 비교하면 전자는 1초 후자는 0.0001초에 끝남

그치만 이런 방식이 정말 확실한 성능 측정의 지표가 될 수 있나?

시간 문제

기기의 사양에 따라 측정의 결과가 다르고 무엇을 하는지에 따라 다르다.

빠른 알고리즘에서는 정말 짧은 시간안에 끝난다 하지만 이중에서도 최선이 존재하는데 이걸 어떻게 알 수 있나?

컴퓨터의 연산 갯수 세기

단순하게 컴퓨터가 몇번의 연산을 해야하는 세는것 컴퓨터의 사양에 관련없이 사용이 가능

아래 알고리즘은 N이 얼마나 크던 3번의 연산에 함수가 끝남

아래는 N만큼의 연산을 수행함

5n+2의 연산이 나오지만 자세한 개수보단 큰그림을 봐야하함

시간복잡도의 시각화

Big O 공식

입력의 크기와 실행 시간의 관계를 의미함

아래 함수는 N의 크기가 실행시간에 어떤 영향도 주지 않음

아래 함수는 5n이지만 상수는 제외한다

아래 함수는 o(n)의 루프가 2개 있지만 O(2n)으로 표시하지 않는다

중첩 루프의 경우

Big O 표시 단순화 하기

기본적으로 상수는 크게 중요하지 않음

산수는 상수다 (더하기, 빼기, 나누기)

변수도 상수

index 로 배열에 접근하는것도 상수

루프는 푸르 길이 * 내부 연산 만약 루프가 하나 더 있다면 (n*m)

공간 복잡도

지금까지는 시간 복잡도를 보았지만 공간 복잡도는 메모리를 얼마나 차지하는지를 보는 것

입력을 제외하고 알고리즘이 차지하는 메모리 영역을 의미함

null, number, undefine 등은 상수 공간을 차지

문자열은 O(n) 공간을 필요로함

자료형 타입도 O(n) 공간이 필요함

입력의 크기에 상관없이 사용하는 공간은 이미 정해져 있음

입력의 크기에 따라 새로운 배열을 리턴하기에 O(n)

로그와 섹션

몇몇 알고리즘은 상수, n, n 제곱 등으로 표현하기 어려운 경우가 있음

그 경우에 등장하는것이 log

Log

지수 함수의