Page 21 -

빅 오 (bi g O )는 알 고 리 즘 의 성 능 상 한 (u p p er b o u n d )을 말 한 다. 그 반 대 인 하 한 (l o w er b o u n d )은 알 고
리 즘 의 복 잡 도 가 초 깃 값 이 후 언 제 나 특 정 함 수 보 다 더 낫 지 않 다 는 것 을 알 때 해 당 한 다. 이 를 빅

인 모 든 n 에 대 해 f(n ) ≥ c g (n ) ≥ 0 을 만 족 하 는 양
오 메 가 (bi g O m e g a ) W (f(n )) 이 라 고 하 며, n ≥ n 0
이 있 다 면 W (f(n )) = g (n ) 으 로 정 의 한 다. 빅 오 와 빅 오 메 가 가 정 의 되 면 동 시 에 상 한
의 상 수 c 와 n 0
과 하 한 의 복 잡 도 둘 다 되 는 상 황 을 정 의 할 수 있 다. 이 것 을 빅 세 타 (bi g T h et a )라 고 하 며, O (f(n ))
= g (n ) 이 고 W (f(n )) = g (n ) 면 W (f(n )) = g (n ) 의 필 요 충 분 조 건 이 된 다 고 말 한 다. 그 러 면 알 고 리 즘

은 상 수 로 스 케 일 링 된 같 은 함 수 로 상 한 과 하 한 의 실 행 시 간 을 갖 고, 알 고 리 즘 의 실 행 시 간 은 해
당 함 수 주 변 범 위 에 놓 인 다 고 볼 수 있 다.

1 . 3 스 택 을 사 용 하 는 주 가 스 팬 R E A L - W O R L D A L G O R I T H M S

이 제 주 가 스 팬 문 제 로 돌 아 가 보 자. 앞 에 서 O (n (n + 1 /2 )) 의 복 잡 도 를 갖 는 알 고 리 즘 을 찾 았 다.
2
이 는 지 금 까 지 설 명 한 복 잡 도 에 따 르 면 O (n ) 와 같 다. 더 잘 할 수 있 을 까 ? 그 림 1 -1 로 돌 아 가 보
자. 여 섯 째 날 일 때 첫 째 날 에 다 다 를 때 까 지 주 가 를 이 전 모 든 날 과 비 교 할 필 요 가 없 다. 우 리 는

모 든 날 을 거 쳐 왔 기 때 문 에 둘 째 날 과 셋 째 날, 넷 째 날, 다 섯 째 날 은 모 두 주 가 가 여 섯 째 날 과 같
거 나 작 음 을 이 미 알 고 있 다. 어 떻 게 든 이 정 보 를 유 지 한 다 면 이 모 든 날 과 비 교 하 는 대 신 에 오 직
첫 째 날 만 비 교 하 면 된 다.

이 것 은 일 반 적 패 턴 인 데, k 일 에 있 다 고 상 상 해 보 라. ( k - 1 ) 일 의 주 가 가 k 일 의 주 가 보 다 낮 거 나
같 으 면, 즉 q u o t e s [ k - 1 ] ≤ q u o t e s [ k ] 또 는 q u o t e s [ k ] ≥ q u o t e s [ k - 1 ] 이 면 다 시 ( k - 1 ) 과
비 교 할 이 유 가 없 다. 왜 ? 미 래 의 어 느 날 인 ( k + j) 일 에 있 다 고 해 보 자. (k + j) 일 의 주 가 가 k 일 의

주 가 보 다 낮 으 면, 즉 q u o t e s [ k + j ] < q u o t e s [ k ] 면 ( k + j) 일 에 시 작 하 는 스 팬 은 k 일 에 서 끝 나 기
때 문 에 ( k - 1 ) 일 과 비 교 할 필 요 가 없 다. (k + j) 의 주 가 가 k 의 주 가 보 다 높 다 면 q u o t e s [ k + j ] ≥
q u o t e s [ k ] 이 고, q u o t e s [ k ] ≥ q u o t e s [ k - 1 ] 이 므 로 q u o t e s [ k + j ] ≥ q u o t e s [ k - 1 ] 이 된 다. 따

라 서 스 팬 의 끝 을 역 으 로 찾 을 때 마 다 조 사 하 는 날 보 다 낮 거 나 같 은 값 인 날 들 을 모 두 제 외 한 다.
그 리 고 미 래 어 느 날 의 스 팬 에 서 도 이 미 제 외 한 날 들 은 고 려 대 상 에 서 배 제 할 수 있 다.
이 해 를 돕 기 위 해 우 리 가 그 림 1 -4 에 서 6 일 기 둥 꼭 대 기 에 앉 아 있 다 고 상 상 해 보 자. 아 래 를 내 려

다 보 지 않 고 똑 바 로 뒤 를 바 라 보 면 오 직 1 일 기 둥 만 보 이 는 데, 이 것 이 바 로 6 일 의 주 가 와 비 교 해

0 3 2

리 얼 월 드 알 고 리 즘( 본 문) 최 종.i n d d 3 2 2 0 1 9 - 0 8 - 1 2 오 후 4: 2 7: 1 0