빅오 표기법(Big-o Notation)

시간 및 공간 복잡도 분석을 위한 표기법 (Big - O) -> 알고리즘의 최악의 경우 복잡도 측정

 

n은 입력의 개수

일반적인 빅오 복잡도

그림의 O(1)은 입력에 따라, 시간이 변하지 않습니다 -> 상수 시간

 

배열의 인덱스를 사용해 접근 하는 경우가 O(1)의 예입니다.

const arr = [1,2,3, ... , 1004, ...]
// 많은 데이터라고 가정
console.log(arr[1004])

인덱스로 접근하는 시간은 정해져 있습니다. 최악의 경우에도 한 번에 접근할 수 있으며, 연결 리스트와 차이를 갖는 배열의 특징입니다.

---

O(n)은 선형 시간이고, 최악의 경우에는 n번 연산해야 합니다.

 

반복문을 통해, 숫자를 출력하는 경우가 O(n)의 예입니다.

 

const linear = n => {
    for(let i = 1; i <= n; i++){
        console.log(i)
    }
}
linear(5)

 

---

O(n²)은 2차 시간입니다 이중 for문을 이용해 숫자, n번 n회를 출력하는 경우에 O(n²)의 예입니다

 

const quadratic = n => {
    for (let i = 1; i <= n; i++){
        console.log(i)
        for (let j = 1; j <= n; j++){
            console.log(j)
        }
    }
}

quadratic(3)

---

O(n³)은 3차 시간입니다 삼중 for문을 이용해 숫자, n번 n회를 출력하는 경우에 O(n³)의 예입니다

 

const Cubic = n => {
    for (let i = 1; i <= n; i++){
        console.log(i)
        for (let j = i; j <= n; j++){
            console.log(j)
            for(let k = j; j <= n; j++){
                console.log(k)
            }
        }
    }
}

Cubic(3)

---

O(log n)

O(log n)은 로그 시간입니다 n의 숫자를 입력받아, 2부터 2^n까지 항목들을 출력하는 경우 O(log n) 예입니다.

 

const log = n => {
    for(let i = 2; i <= n; i = i*2){
        console.log(i)
    }
}
log(5)

---

빅오 표기법 규칙

1. 계수 법칙
2. 합의 법칙
3. 곱의 법칙
4. 전이 법칙
5. 다항 법칙

 

1. 계수 법칙 (係數 coefficient, 因子, 보통 식 앞에 곱해지는 상수) + 현상의 본질적인 구조를 명확하게 한 것

수학에서, 계수(係數)는 변수(문자)에 일정하게 곱해진 상수(숫자)

방정식에서 변수 이외의 부분 즉, 나머지 인수 전체를 의미

 

보통 1은 생략합니다

출처 : https://ko.wikipedia.org/wiki/%EA%B3%84%EC%88%98

 

 저는 식 앞에 곱해진 상수의 구조라고 정의하겠습니다.

 

빅오 표기법에서는 "상수를 제거하라" -> 입력 크기와 연관되지 않은 상수를 전부 무시

 

const addOneToN = n => {
	let result = 0;
    for (let i = 0; i < n; i++){
    	result += 1;
    }
    return result;
}

console.log(addOneToN(5))

위 코드는, 자연수를 입력받고, 자연수만큼 연산한 후 리턴하는 함수입니다.

 

n에 무한이 들어와도, 무한 번 연산이 발생하므로 시간 복잡도는 O(n)입니다. (0부터 n번)

---

const addSixTimesToN = n => {
	let result = 0;
    for (let i = 0; i < 6 * n; i++){
    	result += 1;
    }
    return result;
}

console.log(addSixTimesToN(5))

자연수를 입력받고, 자연수의 6배를 곱한 만큼 연산 후 리턴하는 함수입니다.

 

n에 무한대가 들어오면, 무한 번 * 6 연산이 발생하므로 시간 복잡도는 O(6n)입니다. (0부터 6n번)

 

결론적으로 계수 법칙에서, 무한대 x 무한대나, 무한대 x 6등은, 극한으로 수렴할 시 의미가 없기 때문에 "상수를 제거하라"라는 결론이 도출됩니다.

 

---

합의 법칙은 시간 복잡도를 더할 수 있다는 것입니다.

 

대신, 합의 법칙을 적용한 후 계수 법칙을 적용하여야 합니다.

 

const consensusLaw = n => {
	let count = 0;
    
    for(let i = 0; i < n; i++){
    	count = count + 1;
    }
    
    for(let i = 0; i < 6 * n ; i++){
    	count = count + 1;
    }
    return count;
}

consensusLaw(7);

상단의 함수는 2개의 반복문으로 이루어져 있으며, 첫 번째 반복문의 시간 복잡도는 O(n), 두 번째 반복문의 시간 복잡도는 O(6n)입니다. 두 개를 합치게 되면 O(7n)이며 (합의 법칙) 이후 계수 법칙을 적용해 O(n)이 됩니다.

 

---

곱의 법칙 은 시간 복잡도를 곱할 수 있다는 것입니다.

 

곱한 후에 동일하게, 계수 법칙을 적용합니다.

 

const multiplicationLaw = n => {
    let count =0;
    for (let i=0;i<n;i++){
        for (let i=0;i<6*n;i++){
            count+=1;
        }
    }
    return count;
}

multiplicationLaw(2)

참고 자료에서는 하단의 소스코드를 사용하였는데

 

function a(n){
    var count =0;
    for (var i=0;i<n;i++){
        count+=1;
        for (var i=0;i<5*n;i++){
            count+=1;
        }
    }
    return count;
}

저는 맞다고 생각하지 않아서 제 소스코드를 추가하였습니다

 

중첩 for문에서 외부 for문을 n번, 내부 for문을 6n번 실행합니다(제 소스코드 기준)

 

외부 for문 O(n) * 내부 for문 O(6n) = O(6 n²)이며, 계수 법칙을 적용할 경우 O(n²)이 됩니다.

 

---

전이 법칙

 

교환 법칙 이라고도 부를 수 있으며, 동일한 시간 복잡도를 가지면, 동일한 빅오 표기법을 지닌다

 

계수 법칙에서 사용했던 코드인

 

const addOneToN = n => {
	let result = 0;
    for (let i = 0; i < n; i++){
    	result += 1;
    }
    return result;
}

console.log(addOneToN(5))

위의 예제나

const addTwoToN = n => {
	let result = 0;
    for (let i = 0; i < n; i++){
    	result += 2;
    }
    return result;
}

console.log(addTwoToN(5))

아래의 예제 모두, 출력 값은 다르지만 둘 다 O(n)이며, 같은 방법으로 표기합니다.

---

다항 법칙

 

다항 시간 복잡도가 동일한 다항 차수를 지님

 

const polynomialLaw = n => {
    let count = 0;
    for (let i = 0; i<n*n; i++){
        count = count + 1;
    }
    return count;
}

polynomialLaw(2)

함수의 반복문은 n*n회 반복되며, 시간 복잡도는  \(O^k\)입니다. n*n 회 실행되기 때문입니다

ex n=2, 4회 실행

 

 

---

참고 서적

 

JavaScript Data Structures and Algorithms: An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals

 

자바스크립트로 하는 자료구조와 알고리즘