[Data structures] section2: 빅오 표기법 (Big O Notation)

4. 빅오 (BIG O) 소개

Objectives

• Big O 표기법의 필요성
• Big O 가 무엇인지
• Big O 간단하게 표현하는 법
• 시간 복잡성과 공간 복잡성 정의
• Big O 표기법을 사용하여 여러 알고리즘 평가하기
• 로그 (logarithm)이 무엇인지 

What's the idea here? 

"Write a function that accepts a string input and returns a reversed copy"

제대로 작동하기만 한다면 그것 만으로도 충분하지 않은가? 

 

Who Cares? 

• 코드의 성능을 얘기할 때 정확한 전문 용어를 사용하는 것이 중요합니다.
• 여러 접근법의 장단점을 얘기할때도 유용합니다. 가장 좋은 해결책을 찾는 것이 그렇게 뻔하지는 않습니다. 한 해결책에 정말 좋고 또 하나는 엉망인 경우가 많지는 않습니다.
• 코드를 디버그할때 코드를 느리게 만드는 것은 이해 하는 것이 중요합니다. 에러만을 찾는 것이 아니라, 코드가 작동을 하지만 생각보다 더 오랜 시간이 걸리거나, 브라우저에서 펑션을 실행했을때 컴퓨터가 랙걸린다고 생각해 보세요. 이 섹션에서 언급 할 것들에 대해서 이해하는 것이 도움이 됩니다. 빅오를 이해하면 어디서 문제가 나타나는지 찾기 쉬울 수 있습니다.
• 면접에서 자주 나오는 내용이기 때문에 아는 것이 중요합니다. 

 

5. 코드 시간 재기 

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

//console.log(addUpTo(6))

var t1 = performance.now()
addUpTo(100000000)
var t2 = performance.now()
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds`) // Time Elapsed: 0.15639999997615814 seconds

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


//console.log(addUpTo(6))
var t1 = performance.now()
addUpTo(100000000)
var t2 = performance.now()
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds`) // Time Elapsed: 0.00009999996423721313 seconds

What does better mean?

Faster? Less memory-intensive? More readable? 

 

우선 기기마다 다른 방식으로 시간을 기록합니다.  기기 사양에 따라 다를 수도 있고 그 기계 무엇이 실행 되고 있는지 에 따라서 다를 수도 있습니다. 물론 그렇다고 해서 갑자기 거꾸로 첫 번째 해결 법이 두 번째 갈 것 보다 더 빠르게 나올 수도 있다는 것은 아닙니다. 하지만 차이가 달라질 수 있고 책정된 시간들이 달라질 수 있습니다. 언제나 다른 시간이 기록 될 것입니다.  똑같은 기계가 다른 시간을 기록 할 수도 있습니다. 브라우저 에서 똑같은 코드, 첫 번째 코드에서 조금씩 다른 시간이 기록 되었습니다. 큰 문제는 아니지만 정확하지 않다는 것을 보여 주고 있습니다. 그렇게 때문에 완전히 믿을 수가 없다는 것이죠.

 

세번째는 빠른 알고리즘에서는 정말 짧은 시간 안에 모든 것이 처리 된다는 것입니다. 이런 경우에는 속도 측정 정확도가 충분하지 않을 수 있습니다. 정말 빠른 알고리즘이 세네개 있을 수 있습니다. 하지만 그중에서 가장 빠르고 가장 효율적인 코드가 있을 것입니다. 하지만 저희의 타이밍 function이 그런 작은 차이를 측정하기 힘들다면 아무런 도움이 되지 않습니다.

 

코드를 살펴 보면서 시간을 측정 하지 않고 어느 코드가 더 좋은지 어떻게 평가할 수 있을까요? 정확히 말씀드리면 코드가 실행 되는 시간을 측정 하는 것이 나쁘다는 것은 아니지만, 이런 식으로 코드를 파일 안에 만들고 시간을 측정 하는 방법 외에 더 좋은 방법이 있으면 더 좋을 것이라는 겁니다. 저희 코드가 한 시간이 걸리고 다른 버전이 네 시간이 걸린다고 생각해 보세요. 어떤 게 더 빠른지 알기 위해서 테스트를 실행 하기는 싫거든요. 이렇게 하지 않아도 코드를 비교 하는 특정한 값이 있었으면 좋겠다는 것입니다. 이럴때 빅오 표기법이 유용한 것입니다. 

 

6.  연산 갯수 세기 

Counting Operations

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

1 mutiplication, 1 addition, 1 ivision / 3 simple operations, regardless of the size of n / N이 크든 작든, N의 값과는 상관없이 연산이 3번 이루어지고 있습니다.  

 

function addUpTo(n) {
    let total = 0; (1 assignment)
    for (let i = 1 (1 assignment) ; i <= (n comparisons) n; i++ (n additions and n assignments))) {
    	total += i; (n additions, n assignments)
    }
    return total;
}

다음의 형식으로 모든 연산을 세는 것은 쉽지 않습니다.  5N + 2 / N이 10개라면, 연산 50개에 루프 밖에 있는 2개를 더하므로 52개가 됩니다. 5n + 2이든지, 3n 든지 50n 이든지 상관 없습니다. 중요한 것은 전체적인 추세를 보는 것입니다. 

 

7. 시간 복잡도 시각화하기 

N이 커질수록 걸리는 시간이 비례하게 늘어나고 있습니다. (5N + 2)

https://rithmschool.github.io/function-timer-demo/

 

8. 빅오에 대한 공식 소개 

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

 

Example

function countUpAndDown(n) {
  console.log("Going up!");
  for (var i = 0; i < n; i++) {
    console.log(i);
  }
  console.log("At the top!\nGoing down...");
  for (var j = n - 1; j >= 0; j--) {
    console.log(j);
  }
  console.log("Back down. Bye!");
}

→ O(n)

 

function printAllPairs(n) {
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}

→ O(n * n), n이 커질수록 실행 시간이 n제곱의 값으로 늘어난다는 뜻입니다. 

 

9. 빅오 표현식의 단순화하기 (Simplifying Big O Expressions)

상수는 중요하지 않습니다. Constants Don't Matter 

• O(2n) → O(n)
• O(500) → O(1)
• O(13n^2) → O(n^2)

 

Smaller Terms Don't Matter

• O(n + 10) →  O(n)
• O(1000n + 50) →  O(n)
• O(n^2 + 5n + 8) → O(n^2)

 

Big O SHORTHANDS

1. Arithmetic operations are constant 산수는 상수입니다. (덧셈, 뺄셈, 곱셈, 나눗셈을 포함합니다)

2. Variable assignment is constant. (x = 1000을 처리하는 것과 x = 20000을 하든 100만을 처리하는 것은 비슷한 시간이 걸립니다)

3. Accessing elements in an array (by index) or object (by key) is constant. (인덱스를 사용해서 배열 엘리먼트를 접근하는 것, 배열에서 첫번째 아이템을 찾던지, 10번째 아이템을 찾던지 인덱스를 사용하면 똑같은 시간이 걸립니다.)

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

 

A Couple More Examples

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

→ O(n)

 

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

 → O(1), 5를 넘지 않을 것이므로 n이 커질수록 빅오는 상수라고 단순화할 수 있습니다. <O(5)대신 O(1)> 5보다 크면 무조건 MIN 더 작은 5를 선택할 것이기 때문입니다. n이 1000이더라도 루프가 5번만 반복됩니다. n이 100만이더라도 루프가 5번만 반복됩니다. 

 

 

퀴즈 1: 빅오 (BIG O) 시간 복잡도 퀴즈

0(n + n + n + n) → 0(n)

 

퀴즈 2: 빅오 (BIG O) 시간 복잡도 퀴즈

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;
}

→ 0(n) / for loop 여서...

 

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;
}

 → 0(n^2)

 

10.  공간 복잡도 (Space Complexity)

auxiliary space complexity : 입력되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미합니다. 중요한 것은 알고리즘 자체입니다. 입력보다도 알고리즘 자체가 어떤 영향을 주는지 자세히 봐야 합니다. 공간 복잡도라고 말하는 것은 사실상 보조 공간 복잡도를 말한다고 보면 됩니다. 

 

Rules Of Thumb 

- booleans, numbers, undefined, null) : 불변 공간, 숫자가 1이든 1000이든 상관없음

- Strings : O(n) 문자 길이가 50이라면 길이가 1인 문자열보다 50배 더 많은 공간을 차지함 

- Reference types (arrays, objects) : O(n), 배열의 길이 4, 2를 비교할 때 긴 배열은 2인 배열보다 2배 더 많은 공간 차지함. 

 

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

// O(1) space! 


function double(arr) {
    let newArr = []
    for (let i = 0; i < arr.length; i++) {
        newArr.push(2 * arr[i])
    }
    return newArr // n numbers
}

// 새로운 배열을 만듦. 배열의 크기가 늘어나서 무한대에 가까워질수록 공간 복잡도가 어떻게 되나요? 
// 입력된 배열의 길이가 50이면 그만큼, 100이면 그만큼 리턴하게 된다. 차지 하는 공간은 입력 된 배열의 크기와 비례해서 커지게 됩니다.

 

퀴즈 3: 빅오 (BIG O) 시간 복잡도 퀴즈

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

 → 0(1)

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

 → 0(1)

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;
}

 → 0(n)

 

11. 로그와 섹션 요약

빅오 표기들 중에서 더 어렵거나 흔하지 않은 수학 개념들이 포함되어 있을 수 있습니다. (흔한 표기법 : O(1), O(n), O(n^2)) 그 중 자주 나오는 개념이 로그입니다. 

 

Wait, what's a log agin?

로그함수는 지수함수의 역환입니다. 나눗셈과 곱셈이 짝인 것처럼 로그함수와 지수함수는 짝이다. 

 

log2(8) = 3 <-> 2^3 - 8

2의 몇승의 값이 88이 되나요?

 

---

https://www.udemy.com/course/best-javascript-data-structures/