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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://adam-37.gitbook.io/joomadeung/undefined-2/undefined/big-o.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.