Big O
Big O는 성능, 코드의 효율성을 설명하는 방식으로 , 시간 복잡성과 공간 복잡성을 정의하고 여러 알고리즘을 평가하는데 사용한다.
Big O (보편적인) 시간 복잡도 분석
- 산수는 상수이다. 덧셈, 뺄셈, 곱셈, 나눗셈 등은 Big O 복잡도에 영향을 끼치지 않는다.
- 변수 배정도 상수이다. 변수를 배정하는 것은 메모리에 값을 할당하는 한번의 과정만 있기 때문에 복잡도에 영향을 끼치지 않는다.
- 인덱스를 사용해 엘리먼트를 찾는 것에 key가 제공된다면 복잡도에 영향을 끼치지 않는다
- 루프에서는 루프의 길이 곱하기 루프 내 연산이 복잡도가 된다. 만약 중첩 반복문이라면 n제곱이 된다.
(퀴즈) Big O 표현식 단순화하기
- O(n+10) = O(n)
- O(100 * n) = O(n)
- O(25) = O(1)
- O(n^2 + n^3) = O(n^3)
- O(n + n + n + n) = O(n)
(퀴즈) 시간 복잡도 구하기
1 2 3 4 5 6 7 8 9 10
| 질문 1: 아래 함수에 대한 시간 복잡도를 구하세요.
function logUpTo(n) { for (var i = 1; i <= n; i++) { console.log(i); } }
|
1 2 3 4 5 6 7 8 9 10
| 질문 2: 아래 함수에 대한 시간 복잡도를 구하세요.
function logAtMost10(n) { for (var i = 1; i <= Math.min(n, 10); i++) { console.log(i); } }
|
1 2 3 4 5 6 7 8 9 10
| 질문 3: 아래 함수에 대한 시간 복잡도를 구하세요.
function logAtLeast10(n) { for (var i = 1; i <= Math.max(n, 10); i++) { console.log(i); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 질문 4: 아래 함수에 대한 시간 복잡도를 구하세요.
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; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| 질문 5: 아래 함수에 대한 시간 복잡도를 구하세요.
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; }
|
공간 복잡도 분석
공간 복잡도
알고리즘 자체가 필요로 하는 (메모리) 공간을 의미하며, 보조 공간과 입력이 사용하는 공간이 모두 포함된다.
보조 공간
알고리즘에서 사용하는 추가 공간 또는 임시 공간으로 알고리즘의 일부를 실행하는 데 일시적으로 사용할 수 있는 공간의 양이다.
1 2 3 4 5 6 7 8 9
| function sum(arr){ let total = 0; for(let i = 0; i < arr.length; i++){ total += arr[i] } return total; }
|
1 2 3 4 5 6 7 8 9
| function double(arr){ let newArr = []; for (let i = 0; i < arr.length; i++){ newArr.push(2 * arr[i]); } return newArr; }
|
(퀴즈) 공간 복잡도
1 2 3 4 5 6 7 8 9 10
| 질문 1: 아래 함수에 대한 공간 복잡도를 구하세요.
function logUpTo(n) { for (var i = 1; i <= n; i++) { console.log(i); } }
|
1 2 3 4 5 6 7 8 9 10
| 질문 2: 아래 함수에 대한 공간 복잡도를 구하세요.
function logAtMost10(n) { for (var i = 1; i <= Math.min(n, 10); i++) { console.log(i); } }
|
1 2 3 4 5 6 7 8 9 10
| 질문 3: 아래 함수에 대한 공간 복잡도를 구하세요.
function logAtMost10(n) { for (var i = 1; i <= Math.min(n, 10); i++) { console.log(i); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 질문 4: 아래 함수에 대한 공간 복잡도를 구하세요.
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; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| 질문 5: 아래 함수에 대한 공간 복잡도를 구하세요.
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; }
|
로그(log)
log₂(8) = 3
-> 2³ = 8
log₂(value) = exponent
log
=== log₂
시간 복잡도의 빠르기 나열(빠른 순서대로)
O(1) > O(log n) > O(n) > O(n log n) > O(n₂)