[알고리즘👽] 1. Big O 표기법

💡요약

1. 알고리즘의 효율 측정을 위해 빅오 표기법 사용한다.
2. 빅오는 실행 시간이나 공간 복잡도에 대해 알려준다.
3. 빅오는 정확도가 아니라 전체적인 추세가 중요하다.
4. 빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어에 영향받지 않는다.

빅오란?

어떤 문제에는 해결법이 여러가지가 존재한다. 내가 사용한 방법이 여러 방법 중에서 가장 나은 방법인가? 에 대한 고민을 해결해주는 것이 빅오이다.
빅오는 숫자로 코드의 성능을 표기해준다. 알고리즘 효율성을 비교할 때 빅오 표기법을 사용한다. 알고리즘을 공부하려면 가장 첫 번째로 배워야한다.

코드 시간 재기

function addUpTo1(n) {

    let total = 0;
    for (let i = 0; i < n; i++) {
        total += i;
    }
    return total;

}


function addUpTo2(n) {
    return n * (n + 1) / 2;
}

위의 함수는 특정 숫자까지 모두 더하는 함수이다. 둘 다 똑같이 작동 할때 이 둘 중에 어떤 방법이 더 나은가? 여기서 중요한 건 '더 낫다'라는 건 무엇을 의미할까? 더 빠른 것? 메모리를 덜 사용하는 것? 가독성이 높은 것?
여러가지 중 기본적으로는 속도, 더 빠른 것을 우선적으로 여긴다.

function addUpTo1(n) {
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += i;
    }
    return total;
}



function addUpTo2(n) {
    return n * (n + 1) / 2;
}



const t1 = performance.now();
addUpTo1(100000000);
const t2 = performance.now();

console.log(`첫번째 함수 걸린 시간 : ${(t2 - t1) / 1000} 초`)
// 첫번째 함수 걸린 시간 : 0.0665 초

const t3 = performance.now();
addUpTo2(100000000);
const t4 = performance.now();

console.log(`두번째 함수 걸린 시간 : ${(t4 - t3) / 1000} 초`)
// 두번째 함수 걸린 시간 : 0.00010000002384185791 초

performance.now() 는 함수가 걸린 시간을 측정하는 메소드이다. 두 함수의 걸린 시간을 비교하면 두 번째 함수가 월등히 빠른 것을 확인할 수 있다.
하지만 이런 식의 비교는 불확실하고 신뢰성이 떨어진다. 브라우저나, 컴퓨터 스펙 등의 환경에 따라 측정시간이 달라지고 정말 빠른 알고리즘 같은 경우에는 작은 차이를 구분하기 어렵다.
그럼 시간측정이 아닌 함수의 효율성을 비교하는 방법은 무엇이 있을까?

연산 갯수 세기

시간을 사용하지 않는다면 어떻게 해야할까?
바로 컴퓨터가 처리해야할 연산 개수를 세면 된다. 어떤 알고리즘이 실행되기 위해서 연산이 25개가 실행되고 다른 건 5개가 실행된다면 당연히 후자가 낫다.

function addUpTo2(n) {
    return n * (n + 1) / 2;
}

위의 함수는 연산이 * ,+ ,/ 총 세 개가 존재한다. 즉 n의 값과 상관없이 항상 3번 연산된다.

function addUpTo1(n) {
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += i;
    }
    return total;
}

위의 함수는 반복문을 사용해서 n의 개수만큼 연산된다. n이 5이면 5번, n이 1억이면 1억번. 정확한 연산 개수는 중요하지 않다. 전체적인 추세만 확인하면 된다.

시간 복잡도 시각화

파란색 선이 아까 효율이 좋지 않은 함수, x축에 딱 붙어있는 회색 선이 효율이 좋았던 코드이다.

빅오에 대한 공식 소개

• 빅오는 대략적으로 숫자를 세는 것에 붙인 공식적인 표현이다.
• 정식으로 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명해준다.
• n이 증가할수록 컴퓨터가 해야하는 연산이 결국 n*f(n) 보다 작은 경우 O(f(n)) 이라고 부른다.
• f(n)은 (f(n) = n), (f(n) = n * n ), (f(n) = 1) 모두 가능하다.

빅오 표현식 단순화 하기

O(2n) ❌ O(n) ⭕
O(500) ❌ O(1) ⭕
O(13n^2) ❌ O(n^2) ⭕

O(n + 10) ❌ O(n) ⭕
O(1000n + 50) ❌ O(n) ⭕
O(13n^2 + 10n + 20) ❌ O(n^2) ⭕

상수는 중요하지 않다. 산수는 상수고 변수도 상수고 배열이나 오브젝트에 접근하는 것도 상수다.

공간 복잡도(Space Complexity)

빅오에는 시간 복잡도와 공간 복잡도가 존재한다. 입력이 커질 수록 알고리즘이 얼마나 많은 공간을 차지하는 지에 대한 이야기다. 공간복잡도(auxiliary space complexity)는 입력하는 것을 제외하고 알고리즙 자체가 필요로 하는 공간을 의미한다. n이 커질수록 입력 자체도 커진다.
대부분의 원시값(boolean, numbers, undefined, null)은 불변 공간(constant space) 이다. 그렇기 때문에 입력의 크기와 상관없이, 숫자가 1이든 100이든 모두 불변 공간이라고 여긴다.
문자열은 조금 다르다. 문자열이 1이면 1을 차지하고 50이면 50을 차지한다. O(n) 참조 타입도 문자열과 비슷하다.
참조값은 일반적으로 O(n)의 공간을 갖는다. Array는 길이가 n이고, Object에서는 key의 개수가 n이다.

로그와 섹션

빅오에는 로그가 포함되는 경우가 많다. 나눗셈이 곱셈과 짝인 것처럼 로그함수는 지수함수의 짝이다. 로그 옆에 작은 숫자가 적히지 않으면 2가 숨어있다고 이해하면 된다. 자세히 이해할 필요는 없다. 그저 logn이 그냥 n보다는 효율이 좋다 정도만 알면 된다.