빅오 표기법?

빅오표기법의 필요성

하나의 문제에는 여러가지 해결 방법이 있습니다. 어떻게? 이 중에서 무엇이 가장 좋은 방법인 지 판단할 수 있을까요?

이러한 상황에서 좋은 코드를 판단하기 위해 빅오 표기법이 존재합니다.
단순히 "좋다" "안좋다" 등의 표현은 수치적으로 비교하기 어렵습니다.

성능 좋은 코드가 왜 필요한가? 알고리즘을 왜 알아야하는가?
최적화된 코드는 성능을 향상 시킬 수도 있고, 서버비용을 절약할 수도 있습니다. 그리고 취업 면접에 단골 질문입니다.

코드 시간 재기

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

위의 코드는 1에서 n까지 수를 더하는 함수이자 알고리즘 입니다.

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

코드가 다르지만 위의 코드 또한 1~n 숫자를 더하는 함수 입니다. 결과적으로 위의 두 코드는 같은 결과값을 내보내 주는 알고리즘(함수) 입니다.

• 두 코드 중에 어떤 코드가 더 빠를까요?
• 두 코드 중에 어떤 코드가 메모리를 많이 쓸까요?
• 두 코드 중에 어떤 코드가 더욱 가독성이 좋을까요?

코드의 속도를 판단할 수 있습니다. perfirmance.now() 코드를 활용해서 구할 수는 있습니다만, 좋은 방법이 아닙니다.

• 기기의 사양에 따라 다른 결과값을 보일 수 있습니다.
• 대부분의 알고리즘의 속도가 너무 빠르기 때문에 정확하게 측정하기 어렵습니다.
• 같은 기기라도 측정에 따라 오차가 발생할 수 있습니다.

(만약 하나의 알고리즘이 3시간 걸리고 다른 알고리즘이 8시간 걸리면 두 코드를 3시간 동안 비교할 것인가?)

연산 개수 세기

시간으로 비교하지 못한다면, 무엇으로 비교해야할까요?

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

위의 코드를 하나씩 해보면 곱/더하기/나누기 3번의 연산이 이뤄집니다.

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

위의 코드는 total += 1 부분에서 n개의 더하기와 n개의 = 연산이 이뤄지게 됩니다.
이게 끝이 아닙니다. for문에서 조건도 확인해야하고 i++부분의 연산도 있죠.

간단한 코드지만 연산의 종류와 갯수가 정말 많습니다.

하지만 중요한 것은 "정확한 연산 갯수"가 필요한 것은 아닙니다. 추세적인 것이 중요합니다. n의 개수가 늘어남에 따라 연산의 수가 2n이 되는 지 n^2이 되는 지 전반적인 추세가 중요하다는 것 입니다.

빅오 표현식의 단순화하기

우리가 궁금한 것은 n의 개수가 증가함에 따라 변하는 수치 입니다.
5n+2의 연산이 필요하다면 그냥 n으로 생각할 수 있다는 것이죠

몇가지 예시를 들어 보겠습니다.

• O(2n) -> O(n)
• O(500) -> O(1)
• O(13n^2) -> O(n^2)

작은 연산 숫자들도 중요하지 않습니다.

• O(1000n + 20) -> O(n)
• O(n^2 + 2n + 8) -> O(n^2)

대략적인 순위 입니다
O(1) > O(log n) > O(n) > O(nlog n) > O(n^2)
맨 왼쪽이 가장 좋은 성능이라고 할 수 있습니다.

공간 복잡도

지금까지의 내용은 알고리즘이 시간을 얼마나 사용하는 지에 관한 성능이였다면, 이제는 얼마나 많은 메모리를 사용하냐는 것에 대한 성능입니다.

• booleans, numbers, undefined, mull 은 불변의 공간입니다.
• string 문자열은 O(n)의 공간이 필요합니다. (n은 문자열 길이)
• reference 타입, 배열과 객체도 대부분 O(n)의 공간이 필요합니다.

function sum(arr){
	let total = 0;
    for(let i = 0; i<arr.length; i++){
    	total += arr[i];
    }
}

공간 복잡도를 생각하면서 코드를 확인해보겠습니다.
total 과 i 변수 선언만 존재합니다. 결국 O(1)이라는 것을 확인할 수 있습니다.

function double(arr){
	let newArr = [];
    for(let i = 0; i<arr.length; i++){
    	newArr.push(2*[i]);
    }
    return newArr;
}

n의 값이 늘어남에 따라서 배열의 크기도 n만큼 증가하게 되는 방식입니다.
O(n)으로 단순화 할 수 있습니다.

로그의 개념

알고리즘의 성능 중에서는 o(nlog n) 과 같은 결과를 같은 것들도 있기 때문에 로그의 기본 개념을 알아야합니다.

요약 정리

• 알고리즘의 성능을 분석하기 위해 빅오 표기법이 필요합니다
• 시간이 얼마나 소요되는 지 혹은 공간이 얼마나 사용되는 지가 중점
• 빅오표기법은 입력이 증가함에 따라 소요되는 시간 및 공간의 전반적인 트렌드 입니다. (4n+2 같은 것은 그냥 n 이라는 것 입니다.)
• 시간복잡도 공간복잡도는 하드웨어의 성능에 영향을 받지 않습니다. 오직 알고리즘 그 자체의 성능만 판단 합니다.
• 빅오표기법은 모든 알고리즘에 적용 가능합니다. 연습 필수