[Big O] Timing our code

다음의 문제를 생각해 보자. 

 

Q: Suppose we want to write a function

that calculates the sum of all numbers

from 1 up to (and including) some number n. 

 

If you came up with these two solutions below,

you're going to think about which one is better? 

 

 

solution 1 

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

console.log(addUpTo(7));

 

 

solution 2

function addUpTo(n){
    return n * (n+1) / 2;
}
console.log(addUpTo(6));

 

 

 

what dose better mean before decided it? 

1. faster? -speed

2. less memory-intensive? -space

3. more readable, legible? - readability 

 

among them SPEED, SPACE are important. 

Let's focus on evaluating Speed. 

 

 

---

 

Speed Evaluation 

speed evaluaton을 사용해서 코드가 실행되는 속도로 퀄리티를 측정하는 방법이 있다. 

 

How long does code take to excute? 

the simplest way would be to use sth like

built-in timing functions. 

 

 

solution 1  

 

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

let t1 = performance.now();  //1
addUpTo(1000000000);  //2

let t2 = performance.now();  //3
console.log('Time Elapsed: ${(t2-t1)/1000} seconds.')  //4

 

 

 

( 결과가 제대로 나오지 않음... )

 

performance.now() 메소드 사용

addUpTo 함수 없이 기본 속도. 매번 달라지기는 함 

which in the browser is just going to tell me the number milliseconds

since the document was created, basically since I opened the window. 

 

line 2 I'm going to save that to a variable before I call addUpTo()

I'm going to call addUpTo with what did I do since a billion. 

 

line 3 I'm going to check performance again,

which should have incremented a bunch of milliseconds 

 

Line 4 함수가 돌아갈 때의 속도에서 기본 속도를 뺌. 

 

 

 

 

solution 2  

 

function addUpTo(n){
    return n * (n+1) / 2;
}
var t1 = performance.now();
addUpTo(1000000000);
var t2 = performance.now();
console.log('Time Elapsed: ${(t2-t1)/1000} seconds.')

 

결과 둘다 제대로 나오지 않음.. 

마지막 줄 잘못 적은 듯 

 

 

The problem with Time  Measurement

Different machines will record different times

The same machine will record different times

For fast algorithms, speed measurements may not be precise enough

 

 

위의 방법은 리프레쉬 할 때 마다 바뀌어서  reliable 하지가 않다.

다른 방법을 사용해 보자. 

이 때 Big O를 사용한다. 

 

 

---

Big O 

Rather than counting seconds, 

Let's count the number of simple operations the computer has to perform

 

 

Counting Operations

 

일단은 solution 2를 먼저보자. 

 

solution 2  

1 multiplication

1 addition

1 division

-> 3 operations

 

n 숫자가 몇 인지는 중요하지 않다.

2 이거나 1000,000,000이어도 결과는 같다. 

일반적 흐름은 같다. 

 

 

그래프로 나타내보면 

 

 

 

 

 

solution 1  

 

 

2n operations

2n+2 assignments

n comparisons 

 

n은 숫자가 바뀔 때 마다 매 번 실행해야 한다는 의미이다. 

 

Depending on what we count, 

the number of operations can be

as low as 2n or

as high as 5n + 2

but it doesn't matter bz what we care about is a general trend. 

so in this case, as n grows, the number of operations grow roughly in propertion within. 

 

그래서 결론은

Big O는 n 이다.