CS) Big O Category

Big O category

Big O에 담긴 또 하나의 개념은, Big O의 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다는 것이다.

카테고리는 범주다. 의미 있는 단위로 나누어 파악한다는 뜻이다.

예를 들어 해치백, 스포츠카, 경차, 중형차는 자동차다.
각각 제로백이 몇인지, 몇명을 태울 수 있는지, 연비가 어떻게 되는지는 카테고리에서 중요하지 않다. 설정한 의미 있는 단위에 적합하기만 하면 해당 카테고리에 속한다. 다만 날개가 달려 날아가는 것은 비행기이지 자동차가 아니다.

알고리즘의 효율성도 마찬가지다.

O(N)과 O(N²) 알고리즘을 비교할 때 두 효율성 간 차이가 너무 커서 O(N)이 실제로 O(100N)이든 O(200N)이든 별로 중요하지 않다.
이는 서울과 뉴욕을 14시간만에 주파하는 비행기 입장에서, 스포츠카는 최대 시속 280km, 승용차는 220km를 논하는 것과 같다.

Big O 표기법은 단지 알고리즘에 필요한 단계 수만을 의미하지 않는다.
데이터가 늘어날 때 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하다.

O(N)은 직선 성장을 보여준다. 즉 단계 수가 데이터에 일정 비율로 비례해 직선을 그리며 증가한다. 이와 달리 O(N²)은 지수 성장의 하나다.

지수 성장은 어떤 형태의 O(N)과도 비교되지 않는 완전히 다른 카테고리이다.
O(N)에 어떤 수를 곱하든 데이터가 커지다보면 언젠가 결국 O(N²)이 더 느려진다는 사실을 깨달으면 완벽히 이해가 간다.

따라서 빅 오에서 서로 다른 카테고리에 속하는 두 효율성을 비교할 때 일반적인 카테고리로 분류하는 것으로도 충분하다.

O(1),O(logN),O(N), O(N²) 처럼 지금까지 다룬 Big O 유형이나 앞으로 공부할 유형은 서로 차이가 큰 일반적인 빅 오 카테고리다.

동일 카테고리에 속한 세부사항이 서로 다를 수는 있다.
O(N²)에 속한 버블 정렬과, 선택정렬처럼 말이다.
그렇기 때문에, 서로 같은 카테고리라면, 어떤 알고리즘이 더 빠른지 알기 위해 분석해야 한다.

예제

const printEven1 = (limit) =>{
  let number = 2;

  while(number <= limit){
    if(number % 2 === 0) {
      console.log('Even!')
    }
    number += 1;
  }
}

const printEven2 = (limit) =>{
  let number = 2;

  while(number <= limit) {
    console.log('Even!')
    number += 2;
  }
}

두 함수를 비교해보자. 첫번째 함수는 +1씩 증가하면서 실행되기에 O(N)이고, 두번째 함수는 2씩 증가하기 때문에 O(N / 2)가 될것이다.
하지만 둘다 Big O category에서는 O(N)이다.
두번째 함수가 첫번째 함수보다 2배 더 빠르고 나은 방법이다.
이는 똑같이 Big O에서는 표현되더라도 어떤 알고리즘이 더 빠른지 알아내려면 분석해야 한다는 점을 보여주는 단적인 예다.

printEven1은 N단계가 필요하다.
하지만 정말 딱 N 단계만 필요할까?
나누어 살펴보면 루프 안에서 여러 단계가 일어난다.
첫째로는 if문을 통해 값을 비교하는 단계가 매 루프마다 일어난다.
둘째로는 짝수일 때만 일어나는 출력 단계다.
셋째 매 루프마다 +1씩 더하고 있다.

그렇다면 비교, 출력, number증가 중에 무엇이 제일 중요할까?
정답을 말하자면 모든 단계가 중요하다.
단지 Big O 용어로 단계를 표현할 때 상수를 버리고 표현식을 단순화 했다는 것을 잊지 말아야한다.

Big O는 정확히 무슨 일이 일어나는지 보다는, 실질적으로 루프가 실행되는 횟수에 더 초점을 맞춘 것이기에 분석을 위해서는 모든 단계가 중요함을 잊지 말고 분석해야한다.

또한 알고리즘의 효율성을 비교할 때 고려해야 할 중요한 요인이 또 있다.
지금까지는 알고리즘의 최악의 시나리오에서 얼마나 빠른가에 초점을 맞췄다. 정의에 따르면 최악의 시나리오는 항상 일어나지 않는다. 대체로 일어나는 시나리오는 평균 시나리오다.