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₂)
