[JS 알고리즘&자료구조] Big O 표현식의 단순화

5n + 2라는 식이 있다고 하자. 여기서 연산이 몇개가 더 추가된다고 하더라도 결국 n의 값과 비례하여 실행 시간이 증가하는 추세를 보이기 때문에 Big O 표기법을 적용하면 O(n)으로 표기가 된다.

이 장에서는 Big O 표기법을 단순화하는 몇 가지 방법들에 대해서 살펴보려고 한다. (강사의 경험을 기반으로 하고 있다.) 중요한 것은 큰 그림이라는 점을 기억하자.

1. 상수는 신경쓰지 않아도 된다.

O(2n)이 있다면 그냥 O(n)으로 표기하면 되며 O(500)이 있다면 O(1)로 표시해주면 된다. O(13n²) 또한 상수인 13은 무시한 채로 O(n²)로 표기해준다. 이렇게 표기하게 되면 O(1)이 O(n)보다는 빠르고 O(n)이 O(n²)보다는 빠르다는 사실을 이미 알고 있기 때문에 비교하기가 훨씬 수월하다.

2. 작은 연산들은 신경쓰지 않아도 된다.

O(n + 10)에서 연산을 제외시키고 O(n)으로 표기하고 O(1000n + 50)에서는 상수와 연산을 제외시켜 O(n)으로 표기해준다. 문제는 O(n² + 5n + 8)이다. 해당 표기법에는 n²과 5n이 함께 존재하는 것을 볼 수 있는데 숫자가 커지면 커질수록 5n보다는 n²이 실행 시간에 미치는 영향력이 지대해지기 때문에 O(n²)으로 표기한다.

위에 더해서 Big O 표기법을 단순화할 수 있는 몇 가지 팁을 더 살펴보자. 아래의 팁들은 항상 맞다고 할 수는 없지만 대부분의 상황에 적용시킬 수 있다.

• 산수는 상수이다 : 뺄셈, 덧셈, 나누기, 곱하기
• 변수 배정은 상수이다 : 변수에 값을 할당하는 것은 똑같은 시간을 소요한다
• 인덱스를 통해 배열의 특정 아이템의 접근하거나 키를 통해 객체의 특정 아이템에 접근하는 것의 실행 시간은 상수이다
• 루프의 복잡도는 루프의 길이 곱하기 루프 안의 연산이 된다 : n이 커질수록 실행 시간이 n만큼 늘어나거나 중첩이 있다면 n²만큼 늘어난다