1. 프로그래밍 스타일, 반복과 재귀 - 1.2 선형 탐색에서 Sentinel(보초) 사용

어떤 목적을 달성하기 위한 과정들에 다양한 알고리즘이 존재하고 우리는 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.

시간복잡도 - 알고리즘의 성능을 설명(연산을 수치화)

알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존하며

각 알고리즘의 속도의 평가는 중요하지 않은 상수와 계수들을 제거하여 실행시간에서 중요한 성장률(입력값의 크기에 따른 함수의 증가량) - 점금적 표기법(Asymptotic notation) - 을 측정하여 판단할 수 있다.

이때 최상, 평균으로 측정 시 평가하기가 까다롭기에 최악일 경우를 판단하여 평균과 가까운 성능으로 예측할 수 있다.[빅오 표기법 (Big-O Notation)]

 

예)

N개의 수열을 정렬하는 어떤 프로그램, 즉 이 숫자들을 오름차순으로 배치하는 프로그램은 아래와 같이 실행 시간을 수

치화 할 수 있다.

N 개의 배열에 x를 찾는 코드를 작성하면 아래와 같이 작성할 수 있다.

int a[N], x, i;
i = 0;
while ( i < N && a[i] !=x) i++;

좀 더 성능을 개선 시킬 수 있는 방법을 고민해 보자.

---

1.2 Using a Sentinel in Linear Search

Sentinel(보초)를 써서 개선하는 방법이 있다.

 

아래와 같이 개선을 하면 N번 검색 시 N번의 조건문 검색 시도가 사라진다.

int a[N + 1], x, i;
a[N] = x;
i = 0;
while (a[i] != x) i++;

이런 방식을 '기술' 혹은 '트릭'이라고 부른다고 한다. 가독성 측면에서는 떨어질 수 있지만...