[알고리즘] 상한선(Upper bound), 하한선(Lower bound)

알고리즘 강의를 들을 때마다 단골손님으로 등장하는 몇가지가 있다. 예를들면, 빅오 표기법, 시간 복잡도, 공간 복잡도, 상한선, 하한선,,,

 

오늘은 알고리즘의 상한선, 하한선에 대해 얘기를 해 보도록 하겠다.

 

• 상한선(Upper bound)

어떠한 알고리즘 A의 성능(주로 여기서 성능이란 '시간복잡도'를 의미한다)이 이 이론적 한계(상한선)을 넘지 않을것임을 보장한다는 것. 다시말해, 상한선은 어떠한 알고리즘의 최악의 성능 케이스를 설명할때 사용된다. 예를들어, 어떠한 알고리즘의 시간 복잡도가 최악의 경우O(n^2) 이라면, 이 알고리즘의 상한선은 O(n^2) 이다.

 

• 하한선(Lower bound)

하한선은 알고리즘을 실행할 때 필요한 최소한의 성능을 나타낸다. 이는 주어진 문제를 해결하기 위해 어떤 알고리즘도 이보다 좋은 성능(더 적은 실행 시간이나 공간)을 가질 수 없음을 의미한다. 예를들어, 비교를 통한 정렬문제에 대한 하한선은 O(n log n)이다. 이는 어떤 비교 기반 정렬 알고리즘이든, 최선의 경우에도 n log n에 비례하는 비교 횟수를 넘어서 성능을 향상 시킬 순 없음을 의미한다.

 

• 상한선과 하한선의 중요성

1. 알고리즘 선택: 상한선과 하한선은 특정 문제에 대해 어떤 알고리즘이 가장 효율적인지 결정하는 데 도움을 준다. 예를 들어, 상한선이 더 낮은 알고리즘은 최악의 경우에도 더 좋은 성능을 보일 가능성이 높다.
2. 알고리즘 분석: 알고리즘의 성능을 이론적으로 분석하고 예측하는 데 필수적이다. 이를 통해 알고리즘의 잠재적인 성능 문제를 미리 식별하고 개선할 수 있다.