Big-O Notation

Big-O Notation

알고리즘의 복잡도를 나타내기 위한 worst case 복잡도이다.

 

- 입력값에 대해서 표현된다.

- 작은 디테일보다는 큰 그림에 대해 집중하는 방법이다.

 

Time Complexity

Linear Complexity : O(n)

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

 

위의 소스코드 예시에서 실행되는 구문은 2, 4, 6번 라인에 있는 부분이다.

만약 n이 4라는 숫자가 들어갔다면, 2번 라인은 1번 / 4번 라인은 4번 / 6번 라인은 1번 해서 총 6번

즉, n + 2 라는 식이 나오게 된다. (입력값에 따라서 달라지게 된다는 첫번째 특성)

 

그리고 2라는 숫자는 나중에 n이 막 100,000,000 이렇게까지 커졌을 때는 전혀 중요한 숫자가 되지 않으므로

2라는 숫자는 복잡도에 포함되지 않는다. (큰 그림을 본다는 두번째 특성)

 

그래서 n이 커지면 복잡도도 같이 증가하기 때문에 O(n) 이라는 복잡도를 갖고, linear(선형) 복잡도를 갖는다고 말한다.

그리고 이걸 매번 계산하지 않아도 만약 반복문(for)이 있다면 복잡도는 적어도 O(n) 이 된다.

 

Constant Complexity : O(1)

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

 

위의 예시는 n이 어떤 숫자이든 한 번만 실행되기 때문에 O(1) 복잡도를 가지고, constant(일정한) 복잡도를 갖는다고 말한다.

 

Quadratic Complexity : O(n^2)

for (let i = 1; i <= n; i++) {
	for (let j = 1; j <= i; j++) {
    	// ...
    }
}

 

Cubic Complexity : O(n^3)

for (let i = 1; i <= n; i++) {
	for (let j = 1; j <= i; j++) {
    	for(let k = 1; k <= j; k++) {
        	// ...
        }
    }
}

 

Logarithmic Complexity : O(log n)

입력값이 매번 반복 될 때마다 절반으로 작아질 때

 

공간 복잡도

시간 복잡도와 동일하다.

 

우리가 지향해야 할 복잡도는?

O(log n), O(1) > O(n) > O(n log n) > O(n^2) > O(2^n) > O(n!)