BIG-O 시간복잡도

https://soldonii.tistory.com/56

좋은 코드의 조건

1. Readble  : 읽고 이해할 수 있는가

2. Efficieny  : 메모리를 효율적으로 사용하는가

3. Scalable  : input의 규모가 커져도 느려지지 않는가

 

BIG-O는 코드가 Scalable한 코드인지, 알고리즘을 수행할 때 시간이 얼마나 걸리는지를 측정할 때 사용하는 일종의 언어

컴퓨터는 한정된 메모리 공간만을 가지기 때문에 메모리를 효율적으로 관리해야 한다.

 

 

BIG O의 종류

https://soldonii.tistory.com/56

BIG-O는 input의 증가에 따라서 runtime이 얼마나 빠르게 증가하는지를 측정하는 것이지, 특정 작업이 수행되는데 시간이 얼마나 걸리는지 측정하는 것이 아니다!

 

1. O(1) : Constant Time

상수시간이라 부르며 input이 얼마가 되었든 runtime이 변하지 않는다.

배열에 있는 항목에 인덱스로 접근하는 경우 O(1)만큼의 시간복잡도를 갖는다.

const arr = [1,2,3,4,5];

function exampleConstant(arr) {
    console.log(arr[0]);
}

 

 

2. O(n) : Linear Time

선형시간이라 부르며 최악의 경우 n번의 연산을 수행하는 알고리즘에 적용된다.

for 반복을 통해 n만큼의 숫자를 출력하는 경우 O(n)만큼의 시간복잡도를 갖는다.

const arr = [1,2,3,4,5];

function exampleConstant(arr) {
    for(var i = 0; i < arr.length; i++){
    	console.log(i);
    }
}

 

3.O(n^2) : Quadratic Time

이차시간이라 부르며 loop 안에 loop가 들어가는 경우 복잡도는 +가 아니라 * 가 된다. n*n = n^2

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

 

4. O(log n) : Log

로그 시간 복잡도는 input이 100만정도의 큰 값이 있을 때 효율적으로 사용할 수 있다.

아래 코드처럼 n이 100만일 때, i*2만큼 i가 증가한다면 log2(1000000) = 19.931...으로 19개의 항목만 출력한다.

function exampleLogarithmic(n) {
    for (let i = 2; i <= n; i*2) {
        console.log(i);
    }
}

 

https://soldonii.tistory.com/56

https://soldonii.tistory.com/56

 

출처

자바스크립트에서 Big O(시간 복잡도)란?

 

[Javascript] 시간 복잡도 정리 및 예제