윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석의 핵심 요소

const LSearch = (arr, target) => {
  for(let i=0; i<arr.length; i++){
    if(arr[i] === target) return i; // 찾은 대상의 인덱스 값 반환
  }
  return -1; // 찾지 못했음을 의미하는 값 반환
}

const arr = [3, 5, 2, 4, 9];

let idx = LSearch(arr, 4);
if(idx === -1){
  console.log("탐색 실패");
} else {
  console.log(`타겟 저장 인덱스: ${idx}`);
} // 타겟 저장 인덱스: 3

idx = LSearch(arr, 7);
if(idx === -1){
  console.log("탐색 실패");
} else {
  console.log(`타겟 저장 인덱스: ${idx}`);
} // 탐색 실패

시간 복잡도를 분석해서 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구해보자.
알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 한다. 위의 순차 탐색 알고리즘의 경우에는 < 연산과 ++ 연산이 === 연산에 의존적이다. 비교연산의 수행횟수에 따라 < 연산과 ++ 연산의 수행횟수가 늘거나 줄어든다. 따라서 우리는 === 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다.

순차 탐색 알고리즘을 보면, 찾고자 하는 값이 배열의 맨 앞에 있으면 비교연산의 수행횟수는 1이되고, 찾고자 하는 값이 배열의 가장 마지막에 있거나 아예 저장되어 있지 않으면 비교연산의 수행횟수는 n이 된다. 이처럼 모든 알고리즘에는 가장 행복한 경우와 가장 우울한 경우가 각각 존재하고, 이를 '최선의 경우(best case)' 그리고 '최악의 경우(worst case)'라고 한다.

그런데 알고리즘을 평가하는데 있어서 '최선의 경우'는 관심의 대상이 아니다. 어떤 알고리즘이건 간에 최선의 경우는 대부분 만족할만한 결과를 보이기 때문이다. 데이터의 수가 많아지면, '최악의 경우'에 수행하게 되는 연산의 횟수는 알고리즘 별로 큰 차이를 보인다. 따라서 알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우'이다.

'평균적인 경우(average case)'는 시간 복잡도를 평가하는 정보로 의미를 지니는데, 문제는 이를 계산하는 것이 쉽지 않다. 간단히 말해서 무엇이 평균적인 상황인지 알지 못하기 때문이다. 결국 일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 '최악의 경우(worst case)'가 선택될 수 밖에 없다.

순차 탐색 알고리즘의 시간 복잡도 계산하기: 최악의 경우(worst case)

데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는(비교연산의 횟수는) n이다.

따라서 순차 탐색 알고리즘의 데이터 수 n에 대한 연산횟수의 함수 T(n)은 다음과 같다.