JavaScript 알고리즘 & 자료구조 마스터클래스 - 빅오 표현식 단순화하기

빅오표기법
-N이커지면 N만큼 커지는 것
-N이 커지면 N의 제곱만큼 커지는 것
-N이 커져도 실행시간에 아무 영향도 받지 않는 상수값(단순하게 1이라고 표현함)
-아니면 완전히 다를 수도 있다!

일반적으로 빅오표기법은 가장 높은 실행시간 값을 말하는 것이다.

function addUpTo(n) {
return n * (n + 1) / 2;
}
일때 연산은 3개 뿐이었고, 시간도 상수로 표기된다. O(1)로 표기한다.
이경우 n의 값이 커지더라도 실행시간은 변하지 않는다.

function addUpTo(n) {
let total = 0;
for(let i =1; i <= n; i++) {
total += i;
}
return total;
}
이 함수의 경우 5n인데 5n이던지 10n이던지 상관없이 빅오표기법에서는 단순화한다. O(n)으로! -> 자릿수를 신경쓰기 때문에 5n이든 아니든 상관하지 않는다.

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 = n -1; j >= 0; j--){
console.log(j);
}
console.log("Back down. Bye!");
이 함수의 빅오 찾아보기!
1. n이 늘어날 수록 값이 더해지는 루프가 존재하는지 확인한다.
2. 여기서는 하나씩 더해주는 부분이 O(n)이고, 하나씩 빼는 부분도 O(n)이다.
3. 그렇다면 이 함수의 빅오가 2n일꺼라 생각이 들겠지만, 앞서 이야기 했던대로 자릿수만 중요하기 때문에 2를 빼주고 O(n)의 시간 실행을 가진다.

function printAllPairs(n) {
for(var i = 0; i < n; i++) {
for(var j = 0; j < n; j++){
console.log(i, j);
}
}
}
이런 중첩루프가 포함된 함수일 경우 계산을 어떻게 할까??
O(n) 연산안에 O(n)연산이 있으면 O(n제곱)이 된다.

이런 경우에는 n이 커질 수록 실행 시간이 n제곱의 값으로 늘어난다는 것이다.

빅오 표현식의 단순화하기
1. O(n2 + 5n + 8)일때 멀리서 큰그림만 본다면 n제곱이 가장 소요시간이 길지 5n+8은 빼버려도 큰그림에서 별로 차이가 나지 않는다는 것을 알 수 있다.

100%정확하지 않지만 빅오구하는 꿀팁
1. 산수는 상수다. (덧셈,뺄셈,곱셈,나눗셈)은 상수로
2.변수 배정도 상수이다.(컴퓨터가 변수에 값을 배정하는데 걸리는 시간은 비슷하다)
3.인덱스를 이용해서 아이템을 찾는 것은 첫번째 아이템을 찾던지 10번째 아이템을 찾던지 똑같은 시간이 걸린다.
4.객체를 다루고 데이터를 접근하기 위해서 키가 있다면 그것도 실행 시간이 상수이다.
5. 루프가 있으면 복잡도가 루프의 길이 곱하기 루프 안에 있는 연산들이다.