> For the complete documentation index, see [llms.txt](https://adam-37.gitbook.io/joomadeung/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://adam-37.gitbook.io/joomadeung/undefined-2/undefined/big-o.md).

# big O

**big O표기법이란**

* 여러가지 코드를 일반적으로 서로 비교하고 성능을 평가하는 방법. 한 마디로 **알고리즘의 효율성**을 표기해주는 표기법
* **Big-O(또는 Big-Oh)** **알고리즘의 시간 복잡도**를 나타내는 표기법

**코드를 짤 때 중요한 점**

* faster?
* less memory-intensive?
* more readable?

```jsx
누적된 값 구하기

// 느린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**

```jsx
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**

```jsx
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개가 있다는 뜻

```jsx
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)
```

```jsx
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)
```

```jsx
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)**

```jsx
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)**

```jsx
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)**

```jsx
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)
```