1에서 특정한 N 값과 사이에 있는 모든 숫자를 더하는 함수를 쓰고 싶다!
// 1
function addUpTo(n) {
let total = 0;
for (let i = 0; i <= n; i++) {
total += i;
}
return total;
}
console.log(addUpTo(6));
console.log("--------------------------------------------------------");
// 2
function addUpTo2(n) {
return n * (n + 1) / 2;
}
console.log(addUpTo2(6));
둘 다 답이 정확히 나온다
어떤 것이 나을까?
어떤 코드가 빠르고 어떤 코드가 메모리나 데이터에 대해 효율적이고 어떤 코드가 읽기 쉬울까?
가장 쉬운 것은 타이밍 펑션을 사용하는 것이다.
let t1 = performance.now();
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2- t1) / 1000} seconds.`)사용하면 1번 함수보다 2번 함수가 훨씬 짧은 시간 내에 처리하고 있는 것을 알 수 있다.
기기마다 사양이 다르고 기계에 무엇이 실행되고 있는지에 따라 다르다.
물론 그렇다고 1번 함수가 2번 함수보다 좋은 효율을 보여주지는 않을 것이다.
그럼에도 불구하고 완전히 효율에 대해 단정 지을 수는 없다는 것이다.
그러니 어떻게 시간을 측정하지 않고 알 수 있을까?
이럴 때 BIg O Notation을 사용하면 좋다!
비슷한 개념이지만 정확한 시간을 초로 표현하기 보다는 컴퓨터가 처리해야하는 연산 갯수로 세면 된다!
어떤 컴퓨터는 갯수는 변하지 않기 때문이다.
2번 함수는 1개의 곱하기, 1개의 더하기, 1개의 나누기로 있어서 연산을 총 3번 진행한다.
계산은 딱 3번 한다.
1번 함수는 연산 갯수는 루프안에 있으므로 n에 따라 연산의 갯수가 달라진다.
n의 값이 클 수록 많은 연산을 실행한다.
5n + 2번의 연산을 실행하게 된다. 물론 중요한 것은 전체적인 큰 그림을 보는 것이다.
Big O Notation
Big O 표기법은 알고리즘의 효율성을 설명하는 방법 중 하나이다.
알고리즘의 시간 복잡도나 공간 복잡도를 나타내는데 쓰이는데, 이는 알고리즘의 실행 시간이나 메모리 사용량을 설명하는데 도움을 준다.
Big O 표기법은 주어진 알고리즘의 실행 시간이나 공간 사용량이 입력값의 크기에 따라 어떻게 변하는지를 설명한다.
예를 들어, O(1), O(n), O(n^2) 등으로 표현되는데 O(1)은 입력의 크기에 상관없이 일정한 실행 시간을 의미하고, O(n)은 입력의 크기에 비례해서 실행 시간이 증가하며, O(n^2)는 입력 크기의 제곱에 비례해서 실행 시간이 증가하는 것을 나타낸다.
자바스크립트 알고리즘을 공부하면서 Big O 표기법을 이해하면, 어떤 알고리즘이 입력이 커짐에 따라 얼마나 빨리 혹은 느리게 실행되는지 파악하는 데 도움이 된다.
이는 알고리즘을 최적화하거나, 효율적인 알고리즘을 선택하는 데 큰 역할을 한다.
BIG O는 대략적으로 숫자를 세는 것에 대해 붙인 공식적인 표현이다.
입력의 크기와 실행시간의 관계를 말한다.
전반적인 추세에 대해 주목하는 것이다.
선형적 f(n) = n
제곱 f(n) = n^2
상수 f(n) = 1
2번 함수는 항상 3개의 연산을 실행하므로 O(1)이다.
1번 함수는 n의 수에 따라 달라지므로 O(n)이다.
function countUpAndDown(n) {
console.log("Going up!");
for (let i = 0; i < n; i++) {
console.log(i);
}
console.log("At the Top!\nGoing down...");
for (let j = 0; j >= 0; j--) {
console.log(j);
}
console.log("Back down. Bye!")
}이 함수의 Big O를 찾는다면 우선 볼 것은 n이 커질수록 루프를 실행하는 횟수가 늘어나는 것이다. -> O(n)
function printAllpairs(n) {
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
console.log(i, j)
}
}
}2개의 루프가 있고 이는 n에 의해 작동한다.
n이 커질수록 연산들이 n만큼 증가한다.
중첩되있기 때문에 O(n^2)이다.
가장 중요한 것은 대략적인 큰 그림이다.
상수나 n의 계수등에 대해 신경쓰지말고 큰 그림을 보자
- 산수는 상수다.
- 변수 배정도 상수다.
- 인덱스나 객체에서 접근하는 것은 상수에 가깝다
- 루프로 처리할 때는 루프의 길이에 따라서 큰 그림을 보자.
function logAtLeast5 (n) {
for (var i = 1; i <= Math.max(5,n); i++) {
console.log(i);
}
}
// 5를 신경쓰지 않고 n이 커지는 경우에 대해 생각해서 O(n)이라고 단순하게 생각할 수 있다.
function logAtMost5(n) {
for (var i = 0; i < Math.min(5,n); i++) {
console.log(i);
}
}
// 중요한 것은 n이 커져도 아무런 영향을 주지 않는다는 것이다.
// 왜냐하면 5보다 크면 5번만 반복되기 때문이다.
// 그렇기 때문에 O(1)이라고 단순하게 생각할 수 있다.공간 복잡도
입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는지 생각해보자.
알고리즘 자체에 대해 얼마나 많은 공간을 차지할까
알고리즘 자체가 어떤 영향을 받는지 고민해보자.
불, 숫자, null, undefined는 똑같은 공간을 차지한다.
문자열은 다르다. O(n)의 공간을 차지한다.
Reference 타입, object, array 등도 O(n)의 공간을 차지한다.
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}여기서는 공간에 집중해보자
배열의 길이와는 상관 없이 total이라는 변수가 있고 다른 i라는 숫자가 공간을 차지한다.
이 두 변수는 어떠한 상황에도 존재한다.
따라서 공간 복잡도는 O(1)라고 생각한다.
function double(arr){
let newArr = [];
for (let i = 0; i < arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}배열의 크기가 늘어나서 무한에 가까워 질수록 공간은 어떻게 될까?
새로운 배열을 만드는 코드가 있고 또한 입력 값에 따라 차지하는 공간은 입력된 배열의 크기와 비례해서 커지게 된다.
따라서 공간 복잡도는 O(n)이라고 생각한다.
어떤 알고리즘은 O(1), O(n), O(n^2)처럼 Big O가 간단하지 않은 경우가 있다.
그런 경우들은 흔한 복잡도다. 다른 수학 개념이 있을 수 있다.
예를 들면 로그 같은 경우가 있다.
이 케이스도 로그를 크게 이해하려고 하지 않고 큰 그림을 봐서 어떤 알고리즘이 더 효율적인가에 대해 생각하면 된다.
