상한보다 최악이 있는가 헷갈리는 부분이라 고민을 해보고 싶어서 작성한다. 먼저 시간 복잡도에서 빅오는 충분히 큰 입력을 가정하며, 입력에 대한 연산수로 알고리즘의 실행 시간을 표기하는 방법이다. 이 때 빅오는 상한, 빅오메가는 하한, 빅세타는 평균의 의미로 사용한다. 그런데 나는 상한(Upper Bound)라는 말이 왜 최악과 같지 않은지 와닿지 않았다. 위와 아래로 일정한 범위를 이루고 있을 때, 위쪽의 한계 상한의 정의는 위쪽의 한계. 이보다 더 높을 수 없기 때문에 시간을 기준으로 가장 오래걸리는 최악이다. 그런데 왜 최악과 상한을 분리시켜 봐야하는가? 그림을 그려보았다. 알고리즘에는 입력 데이터의 수, 그리고 정렬의 경우 데이터 배열에 의해 최선/최악의 연산수가 결정된다. 어떤 알고리즘의 연산수가..
