[8일차] Big O notation

서론

어제의 이야기를 이어서 하도록 하겠다.

본론

Big O 표기법(Big O notation)

Big O 표기법은 기본적으로 O() 형태에 괄호 안에 연산 갯수의 근사치를 넣는다.
저번 게시글의 첫번째 코드를 다시 봐보자

<script>
	function addAll(n){
    	var total = 0; 
    	for(var i = 0; i<=n; i++){
			total += i; 
        } 
        
        return total;
    }
    
    console.log(addAll(n));
</script>

여기서는 for문 루프를 사용해서 0부터 N까지 연속된 숫자들을 더했다. for문 루프를 사용했기 때문에 total+=i는 N번 동안 실행된다. N이 늘어나면 또 그만큼 연산이 늘어나고, 줄어들면 비례해서 줄어든다. 그렇기 때문에 여기서 Big O는 O(n)으로 표기한다.

이번에는 두번째 코드를 다시 봐보자.

<script>
	function addAll2(n){
    	return n*(n+1)/2;
	}

	console.log(addAll2(n));
</script>

여기서 연산의 갯수는 N의 증감에 영향을 받지 않는다. N이 커지든, 작아지든 addAll2안에서 곱하기, 더하기, 나누기 연산이 똑같은 횟수로 실행된다. 이렇게 상수로 연산의 갯수가 고정되어 있다면 Big O를 O(1)로 표기한다.

이런식으로 연산이 얼마나 진행되는지 대략적인 추세를 파악하여 효율적인 알고리즘을 세울 수 있다.
다음 그림에서는 어떤 것이 더 실행이 효율적인지를 Big O표기법을 이용해 가시적으로 보여준 그래프이다.

이 그래프를 보면 상수일때 가장 좋고 n에 의해 영향을 많이 받으면서 연산이 많아지면 좋지 않다고 표현하고 있다.

여기까지 우리는 얼마나 빠른 시간내에 진행이 되는지 Big O의 시간복잡도에 대해서 이야기를 했다.
다음글에서는 공간복잡도에 대해서 이야기 해보도록 하겠다 다음 이시간에~

참고

사진 출처 : https://www.bigocheatsheet.com/