빅오 표기법과 시간 복잡도
어떤 문제에 대해 여러 가지 해결방식이 있을 때 각 알고리즘의 효율성을 나타내는 표기법
예를 들어, 1부터 n까지의 합을 구하는 함수를 구현할 때 여러 방법이 있지만 for문과 단순 공식을 사용하는 방법으로 각각 구현해서 수행된 시간을 구해보면
// 방법1
function add(n) {
let sum = 0
for (let i = 1; i < n; i++) {
sum += i
}
return sum
}
const time1 = performance.now()
add(100000000)
const time2 = performance.now()
console.log((time2 - time1) / 1000) // 1.0271000000005588s// 방법2
function add2(n) {
return (n * (n + 1)) / 2
}
const time1 = performance.now()
add2(1000000000)
const time2 = performance.now()
console.log((time2 - time1) / 1000) // 0.xxxs위 두 방법을 비교하면 두 번째 방법이 더 좋은 코드로 보이는데 기기마다 그리고 상황마다 다를 수 있기 때문에 이런식으로 시간의 차이로 측정하는 방법은 정확하지 않을 수도 있다.
이렇게 하지 않아도 코드의 성능을 비교하는 특정한 값 또는 척도로 나온게 빅오 표기법이고 이럴 때 빅오 표기법이 유용한 것이다.
시간을 측정하지 않고 연산의 개수를 세보면 해당 코드의 성능을 알 수 있다. 연산의 개수는 기기마다 그리고 상황마다 다르지 않고 어떤 컴퓨터에서든지 동일하며 시간은 항상 연산의 개수에 달려 있기 때문이다.
방법2를 보면 n이 1만이든 10억이든 연산은 딱 3번만 이루어져서 상수 시간만큼 소요된다. 하지만 방법1에서는 n의 값이 증가함에 따라 연산의 횟수또한 증가하기 때문에 상당한 시간이 걸릴 수 있다. 즉, 5n+2 만큼의 연산이 이루어질수 있다.
- 해당 알고리즘의 효율성을 나타내는 지표
- 빅오는 이런 숫자를 세는 방식에 붙인 공식적인 표현이라고 할 수 있으며
- 입력된 내용에 따라 알고리즘 수행 시간이 어떻게 변하지는에 대한 방식이라고도 할 수 있다. 즉, 입력의 크기와 실행 시간의 관계이다.
모든 연산들을 일일이 다 세는 것은 힘들뿐 정확한 개수는 별로 중요하지 않고 전체적인 추세를 중요하게 여긴다.
그래서 방법1에서 연산의 개수가 5n+2일 때 n으로 단순화할 수 있다.
빅오 표기법과 공간 복잡도
입력이 커질수록 알고리즘이 얼마나 많은 메모리 공간을 차지하는지에 대한 것
몇 가지 규칙들이 있는데
-
불리언, 숫자, undefined, null은 모두 자바스크립트에서 불변 공간이다.
예를 들어, 숫자가 10이든 10000이든 true이든 false이든 똑같은 공간을 차지한다는 것이다.
-
문자열은 O(n) 공간이 필요하다. 만약 50자라면 문자열의 길이가 1인 문자열보다 50배 더 많은 공간을 차지하게 된다.
-
참조 타입인 배열과 객체에서도 O(n) 공간이 필요하다. (이때 n은 배열의 길이이거나 객체의 key 갯수이다.) 만약 배열의 길이가 4이고 다른 배열의 길이가 2라면 약 2배 더 많은 공간을 차지하게 된다.
아래 예시에서 배열을 받아서 그 배열 요소들의 합을 구하는 코드가 있을 때
// 예시1
function sum(arr) {
let total = 0
for (let i = 1; i < arr.length; i++) {
total += arr[i]
}
return total
}공간을 차지하는 것에는 total과 i 변수가 있다. 배열의 크기에 상관없이 이미 두 개로 정해진 것이다. 즉, 입력의 크기가 차지하는 공간과는 관련이 없다. O(1) 공간인 것이다.
두 번째 예시에서는 전달되는 배열의 각 요소들에 2를 곱해서 새로운 배열을 반환하는 코드인데
// 예시2
function double(arr) {
let newArr = []
for (let i = 0; i < arr.length; i++) {
newArr.push(arr[i] * 2)
}
return newArr
}공간을 차지하는 것에는 newArr 변수가 있다. 하지만 예시1과는 다르게 전달되는 배열의 길이가 커질수록 이 변수가 차지하는 공간 또한 커진다는 것이다. O(n)
