빅 오(Big O)

시간 복잡도

• O(1) : n의 값이 커지더라도 연산의 개수(=>실행시간)는 변하지 않는다.
• O(n) : n의 값이 커지면 연산의 개수(=>실행시간)도 n개로 변한다.
• O(n²) : O(n) 안에 O(n) 중첩 e.g. 이중 for문

표기법	간단 빅 오 표기법
O(2n)	O(n)
O(500)	O(1)
O(13²)	O(n²)
O(n+10)	O(n)
O(n² + 5n + 8)	O(n²)

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

- Math.max : 주어진 값 중 가장 큰 값을 반환 => 따라서 n에 값에 따라 for문 안의 연산의 갯수가 n번 실행된다.
즉, O(n)

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

- Math.min : 주어진 숫자들 중 가장 작은 값을 반환 => 따라서 n의 값이 크더라도 최소 5번만 실행된다.
즉, O(1)

---

공간복잡도

• Javascript
  • Boolean, number, undefined, null 모두 불변으로 똑같은 공간을 차지한다. O(1)
  • String O(n)만큼 공간을 차지한다.
  • Reference type(arrays, object) 모두 O(n)만큼 공간을 차지한다.

---

로그(log)

로그는 지수를 다른 방법으로 표현한 것

https://ko.khanacademy.org/math/algebra2/x2ec2f6f830c9fb89:logs/x2ec2f6f830c9fb89:log-intro/a/intro-to-logarithms

로그란? (개념 이해하기) | 로그 | Khan Academy

 

본 내용은 udemy - Javascript 알고리즘 & 자료구조 마스터클래스의 강좌 내용을 바탕으로 작성하였습니다.