알고리즘 실행 시간과 Big O, Big Ω 표기법

알고리즘의 실행 시간을 이해하는 데 중요한 개념이 Big O와 Big Ω 표기법이다. 처음 접할 때는 복잡하게 느껴질 수 있지만, 실제로 알고리즘을 평가할 때 매우 유용한 도구가 된다. Big O와 Big Ω 표기법에 대해 간단하고 명확하게 정리해보자.

 

1. Big O 표기법: 실행 시간의 상한

Big O는 알고리즘 실행 시간의 상한을 나타낸다. 즉, 최악의 경우에 얼마나 시간이 걸릴지를 보여주는 것이다. 알고리즘이 실행되는 데 필요한 시간이 입력 크기(n)가 커짐에 따라 어떻게 변화하는지 알 수 있다. 예를 들어, O(n)이라고 쓰이면, 알고리즘의 실행 시간이 데이터 크기(n)가 늘어날수록 선형적으로 증가한다는 의미다.

ex.

• O(n): 선형 검색 알고리즘은 데이터가 하나일 때는 1번만, 10개일 때는 10번, 100개일 때는 100번씩 검색을 해야 한다. 이 경우 실행 시간은 O(n)으로 표현된다. 즉, 데이터 크기(n)가 늘어날수록 실행 시간도 비례해 증가한다.
• O(n²): 버블 정렬과 같은 알고리즘은 데이터 크기(n)가 커지면 실행 시간이 n의 제곱만큼 늘어난다. 예를 들어, 데이터가 10개일 때는 100번, 100개일 때는 10,000번 정도 계산이 필요하다.

참고: O(n/2)와 같은 표현은 결국 O(n)으로 간단히 바꿀 수 있다. 왜냐하면, n이 매우 커지면 나누기 2는 실행 시간에 큰 영향을 미치지 않기 때문이다.

 

2. Big Ω 표기법: 실행 시간의 하한

Big Ω는 알고리즘 실행 시간의 하한을 나타낸다. 즉, 최선의 경우 얼마나 시간이 걸릴지를 나타낸다. 예를 들어, 선형 검색 알고리즘은 데이터를 1번만에 찾을 수도 있지만, 최악의 경우에는 모든 데이터를 다 확인해야 한다. 이때 Big Ω는 알고리즘이 최선의 경우 걸릴 최소 시간을 나타낸다.

ex.

• Ω(1): 어떤 알고리즘이 특정 조건에서 1번만에 결과를 얻을 수 있다면, 그 알고리즘의 하한은 Ω(1)이 된다. 최소한 1번의 계산은 필요하다는 의미다.
• Ω(n): 선형 검색에서는 데이터가 한 번에 발견될 수도 있지만, 모든 데이터를 하나씩 확인해야 할 수도 있다. 그래서 하한은 Ω(n)으로 나타낼 수 있다.

3. 실행 시간의 상한과 하한, 어느 것이 더 중요할까?

상한(Big O)이 낮은 알고리즘이 더 좋은 경우가 많다. Big O는 알고리즘의 최악의 경우 얼마나 시간이 걸릴지를 나타낸다. 즉, 알고리즘이 최악의 상황에서 얼마나 비효율적일지를 예측할 수 있다. 예를 들어, O(n)은 O(n²)보다 실행 시간이 더 빠르다. 데이터가 많을수록 O(n²) 알고리즘은 실행 시간이 급격하게 늘어나기 때문에 비효율적이다.

반면, Big Ω는 알고리즘이 최선의 경우 얼마나 빠를 수 있는지를 나타낸다. 예를 들어, Ω(1)이면 알고리즘이 항상 최소 1번만에 끝날 수 있다는 뜻이다. Big Ω는 알고리즘이 최적의 성능을 낼 수 있는 조건을 이해하는 데 유용하다.

 

결론적으로, Big O는 알고리즘의 최악의 경우를 고려한 효율성을 평가하는 데 더 중요한 역할을 한다.

 

---

+ 정리

• Big O는 알고리즘 실행 시간의 상한을 나타낸다. 실행 시간이 최악의 경우에 얼마나 걸릴지를 알려준다.
• Big Ω는 알고리즘 실행 시간의 하한을 나타낸다. 최선의 경우 실행 시간이 최소 얼마나 걸릴지를 보여준다.

따라서 알고리즘의 효율성을 평가할 때, Big O는 주로 최악의 경우를 고려하여 실행 시간을 비교하고, Big Ω는 알고리즘이 최선의 조건에서 얼마나 빠를 수 있는지 파악하는 데 유용하다(: