[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 2: 빅오 표기법)

섹션 2: 빅오 표기법(Big O Notation)

📌 Big O

Big O는 코드의 성능을 숫자로 표현하는 것이다.

What does better mean? Faster? Less memory-intensive? More readable?

 

📌 시간 복잡도(Time Complexity)

1~n까지의 합을 구할 때 for문을 이용하는 방법과, 수학 공식 n*(n+1)/2를 이용하는 방법을 비교해 보자!

// 코드 수행 시간 측정
var time1 = performance.now()
addUpTo(1000000000)
var time2 = performance.now()
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)

위 코드와 같은 방식으로 코드의 시간을 측정해 비교할 수 있다. 하지만 빅오 표기법을 이용한 다면 테스트를 해보지 않고서도 성능을 비교할 수 있다.

 

1) Big O는 연산의 개수를 세는 것으로 성능을 표현

• n * (n + 1) / 2는 3번 연산, n의 개수와 상관없음 → O(1)
• for문은 n의 개수만큼 연산이 비례적으로 늘어남 → O(n)
• 중첩 for문은 n의 개수에 제곱으로 늘어남 → O(n²)

 

2) 상수를 없애고 단순화된 것들만 비교

• O(2n) → O(n)
• O(500) → O(1)
• O(13n²) → O(n²)

 

3) 더 작은 값은 안 중요

😉우주에서 내려다 본다고 생각해 보라!

• O(n + 10) → O(n)
• O(1000n + 50) → O(n)
• O(n² + 5n + 8) → O(n²)

 

4) 주요 개념

1. 산수는 상수 실행 시간
2. 변수 배정도 상수 실행 시간
3. 배열에서 인덱스를 찾는 것, 객체의 키를 찾는 것 상수 실행 시간
4. 루프는 n, 중첩 루프는 n²

 

5) 예제 코드

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

// O(1)
// 반복 횟수가 언제나 5이하 이기 때문
function logAtLeast5(n) {
  for (var i = 1; i <= Math.min(5, n); i++) {
    console.log(i);
  }
}

 

📌 공간 복잡도(Space Complexity)

공간 복잡도는 입력이 커지면서 얼마나 많은-메모리-공간을 차지하는가를 나타내는 것이다.

• 대부분의 기본 자료형은 상수 O(1)
• 문자열 자료형은 O(n)
• 참조 자료형은 O(n)

 

📌 Logarithm Complexity

[그림 1] Logarithm Complexity (출처: Udemy JavaScript 알고리즘 & 자료구조 마스터클래스)

 

로그함수는 지수함수의 역함수이다. 나눗셈과 곱셈이 짝인것처럼 로그함수와 지수함수는 짝인 것이다.

log₂(8) = 3 → 2³ = 8
log₂(value) = exponent → 2^exponent = value

[그림 1]과 같이 효율적인 알고리즘은 대부분 로그와 관련 있다.