3.2.2 같은 알고리즘, 다른 시나리오

2장에서 배웠듯이 선형 검색이 항상 O(N)은 아니다. 찾고 있는 항목이 배열의 마지막 셀에 있다면 찾는 데 N단계가 걸린다. 하지만 원하던 항목을 배열의 첫 번째 셀에서 찾았다면 선형 검색은 단 한계 만에 항목을 찾은 것이다. 따라서 이러한 선형 검색 사례는 O(1)이라 할 수 있다. 전체적인 관점에서 선형 검색의 효율성을 설명한다면 최선의 시나리오에서는 O(1), 최악의 시나리오에서는 O(N)이라 할 수 있다.

빅 오가 주어진 알고리즘의 최선과 최악의 시나리오를 효과적으로 설명하긴 하지만, 별도로 명시하지 않는 한 빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다. 선형 검색이 최선의 시나리오에서 O(1)일 수 있음에도 대부분은 O(N)이라 설명하는 이유가 여기에 있다.

이는 “비관적인” 접근이 유용한 도구일 수 있기 때문이다. 최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 알면 최악을 대비함과 동시에 알고리즘의 선택에 중요한 영향을 미칠 수 있다.