big O

big O표기법이란

• 여러가지 코드를 일반적으로 서로 비교하고 성능을 평가하는 방법. 한 마디로 알고리즘의 효율성을 표기해주는 표기법

• Big-O(또는 Big-Oh) 알고리즘의 시간 복잡도를 나타내는 표기법

코드를 짤 때 중요한 점

• faster?

• less memory-intensive?

• more readable?

누적된 값 구하기

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

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

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

var time1 = performance.now();
addUpTo(1000000000);
var time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`);
// Time Elapsed: 0.9598000000119209 seconds.

빠른 ver은 addUpTo(n) 의 n에 어떤 숫자가 오더라도 3번의 연산만 하면 된다.

(n * (n + 1)) / 2; : * + /

그렇기 때문에 연산 시간은 매번 거의 같다.

빠른ver O(1)

느린ver O(n)

---

ex) 1

function countUpAndDown(n) {
  console.log('Going up!');
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
// 시간복잡도: O(n)
  console.log('At the top! \\nGoing down...');
  for (let j = n - 1; j >= 0; j--) {
    console.log(j);
  }
// 시간복잡도: O(n)
  console.log('Back down. Bye!');
}

Going up!
0
1
...
9
At the top! 
Going down...
9
...
1
0
Back down. Bye!

10n

O(n) 연산은 countUpAndDown(n) 의 n값에 바인딩된다.

ex) 2

function printAllPairs(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
    // 시간복잡도: O(n)
  }
  // 시간복잡도: O(n)
}

여기서의 big O는 O(n^2)

---

big O 표현 단순화하기

O(2n) → O(n)

O(500) → O(1)

O(13n^2) → O(n^2)

• O(500)은 연산 갯수가 어떤 상황에든 500개가 있다는 뜻

function logAtLeast(n) {
  for(let i = 1; i <= Math.max(5, n); i++){
    console.log(i);
  }
}
// 시간복잡도: O(n)

function logAtMost5(n) {
  for(let i = 1; i <= Math.min(5, n); i++){
    console.log(i);
  }
}
// 시간복잡도: O(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;
}
// 시간복잡도: O(n)

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)

---

공간복잡도

ex 1)

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

// 공간복잡도: O(1)

total 변수에 0이라는 숫자 할당

i변수에 0이라는 숫자 할당

그러므로 O(1)공간

ex 2)

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

// 공간복잡도: O(n)

arr 의 길이가 50이면 newArr에 50의 길이만큼 리턴한다.

차지하는 공간은 입력된 배열의 크기와 비례해서 커진다. 그러므로 O(n) 공간

ex 3)

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)