1. Big O Notation(표기법)

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스 :: 섹션 2 빅오 표기법(Big O Notation)

 

빅오(Big O) - 여러가지 코드를 일반적을 서로 비교하고 성능을 평가하는 방법입니다.

 

Timing function

performance.now(); 활용해서 함수 작동 시간 확인하기

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

let t1 = performance.now();
addUpTo(10000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2-t1) / 1000} seconds`)

콘솔에 => Time Elapsed: 0.0175 seconds

---

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

=> for문보다 빠름. n 값과는 상관없이 연산 3번(곱하기, 더하기, 나누기) 일어남.

=> for문에서 total += i 를 보면 n 번의 더함(additions)과 n 번의 equal(assignments)이 있고, i++에도 n 번의 더함(additions)과 n 번의 assignments 이 있다. 그리고, let total = 0; let i = 1;은 각각 1 assignment, i <= n; 은 n번의 비교(comparisons)가 있다.

---

Introducing... Big O

Big O Notation is a way to formalize fuzzy counting.

It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow.

We won't care about the details, only the trends.

 

입력의 크기와 실행시간의 관계를 말한다.

 

Big O Definition

We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases.

 

Big O Shorthands

-Analyzing complexity with big O can get complicated

-There are several rules of thumb that can help

-These rules won't ALWAYS work, but are a helpful starting point

1. Arithmetic operations are constant

2. Variable assignment is constant

3. Accessing elements in an array (by index) or object (by key) is constant

4. In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

---

Quiz

아래 함수에 대한 시간 복잡도를 구하세요.
질문 1:

    function logUpTo(n) {
        for (var i = 1; i <= n; i++) {
            console.log(i);
        }
    }
    
답: O(n)    
질문 2:

    function logAtMost10(n) {
        for (var i = 1; i <= Math.min(n, 10); i++) {
            console.log(i);
        }
    }
    
답: O(1)    
질문 3:

    function logAtLeast10(n) {
        for (var i = 1; i <= Math.max(n, 10); i++) {
            console.log(i);
        }
    }

답: O(n)
질문 4:

    function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;
}

답: O(n)
질문 5:

    function subtotals(array) {
        var subtotalArray = Array(array.length);
        for (var i = 0; i < array.length; i++) {
            var subtotal = 0;
            for (var j = 0; j <= i; j++) {
                subtotal += array[j];
            }
            subtotalArray[i] = subtotal;
        }
        return subtotalArray;
    }
    
답: O(n^2)

---

공간복잡도(Space Complexity)

Space Complexity in JS (Rules of Thumb)

- Most primitives(booleans, numbers, undefined, null) are constant space.

불리언, 숫자, undefined, null은 자바스크립트에서 모두 불변 공간입니다. 입력의 크기와는 상관 없이, 숫자가 1이든 1000이든 모두 불변 공간이라고 여깁니다 불리언이 true or false 든 똑같은 공간을 차지.

 

- Strings require O(n) space(where n is the string length)

- Reference types are generally O(n), where n is the length (for arrays) or the number of keys (for objects)

example

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

=> 공간복잡도는 O(1) space! 

=> let total = 0; 에서 숫자 하나, let i = 0; 에서 숫자 하나 차지!

 

Quiz

아래 함수에 대한 공간 복잡도를 구하세요.
질문 1:

    function logUpTo(n) {
        for (var i = 1; i <= n; i++) {
            console.log(i);
        }
    }

답: O(1)
질문 2:

    function logAtMost10(n) {
        for (var i = 1; i <= Math.min(n, 10); i++) {
            console.log(i);
        }
    }

답: O(1)
질문 4:

    function onlyElementsAtEvenIndex(array) {
        var newArray = Array(Math.ceil(array.length / 2));
        for (var i = 0; i < array.length; i++) {
            if (i % 2 === 0) {
                newArray[i / 2] = array[i];
            }
        }
        return newArray;
    }
    
답: O(n)
질문 5:

    function subtotals(array) {
        var subtotalArray = Array(array.length);
        for (var i = 0; i < array.length; i++) {
            var subtotal = 0;
            for (var j = 0; j <= i; j++) {
                subtotal += array[j];
            }
            subtotalArray[i] = subtotal;
        }
        return subtotalArray;
    }
    
답: O(n)

https://cs.slides.com/colt_steele/big-o-notation

Big O Notation