Big-O Notation - 시간 복잡도

이번 포스트에서는 알고리즘 간 효율성을 비교할 때 주로 사용하는 시간복잡도를 표현하는 방법에 대해서 알아보겠습니다.
들어가기 전에 앞서 알고리즘 간 비교는 항상 최악의 시나리오를 염두에 두고 비교한다는 것을 인지하시고 읽으시면 표기법에 대해 이해하는 데에 도움이 되겠습니다.
그럼 시작하겠습니다.

---

1. Big-O 표기법

 Big-O 표기법은 시간 복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 표현하기 위해 수학적 개념을 차용한 것입니다.

"데이터 원소가 N개 일 때 알고리즘에는 몇 단계가 필요한가"

표현한 것이라고 보시면 되겠습니다.

 

예시를 들어 보겠습니다.

N개의 원소를 가진 배열을 선형 검색한다면 몇 단계가 필요할까요? 

네, 맞습니다. N단계가 필요합니다.

우리는 이를 선형 시간 알고리즘이라 부르고 이를 Big-O 표기법으로는 $O(N)$ 으로 표기합니다.한번 더해 볼까요?

 

배열의 특정 인덱스를 읽는 연산은 몇 단계가 필요할까요?
1단계가 필요합니다.

이것을 상수 시간 알고리즘이라 부르고  Big-O 표기법으로는 $O(1)$ 로 표기 할 수 있습니다.

어렵지 않죠?

---

2. Big-O 의 본질

한 가지만 더 해보겠습니다. 

데이터 크기에 관계없이 항상 3단계가 걸리는 알고리즘이 존재한다고 할 때 이 알고리즘의 시간 복잡도는 얼마일까요? 

놀랍게도 $O(3)$ 이 아닌 $O(1)$입니다.

 

 

왜일까요?

그 해답은 Big-O의 본질에 있습니다.

Big-O의 본질은 단순히 알고리즘의 단계가 아닌 데이터가 증가할 때 변화하는 알고리즘의 성질을 표현한 것 이기 때문입니다.

즉 데이터 변화 측면에서 상수인 3은 $O(3)$ 이거나 $O(1)$ 이거나 시간의 변화가 없는 같은 유형인 것입니다.

이해가 어렵다면 항상 데이터가 무한히 증가한다고 생각해 보는 것도 도움이 됩니다.

---

3. Big-O 계산 시 특성

• 식 내의 상수는 버립니다.
  • $O(3N^2)$ = $O(N^2)$
  • $O(5)$ = $O(1)$

 

• 두 가지 항이 있을 때, 변수가 같으면 큰 것만을 남기고 제거합니다.
  • $O(N^2 + N)$ = $O(N^2)$
  • $O(N^2 + NlogN)$ = $O(N^2)$

 

• 두 가지 항이 있는데 변수가 다르면 유지합니다
  • $O(N^2 + M)$

---

마치며

이번 포스트에서는 시간 복잡도에 대해서 알아보았습니다.
극한의 개념에 대해 익숙하신 분이시라면 어렵지 않게 익히셨겠지만, 그렇지 못한 분들은 낯선 접근법에 어려움을 겪으실 거라 생각됩니다.
하지만 어렵지 않은 개념이기에 충분한 시간을 가지고 천천히 반복해서 예시를 보고 Big O Notation이 어떤 필요성에 의해 만들어졌는지를 고민해 보시면 금방 이해하실 수 있으실 거라 믿습니다.
감사합니다.