[Java 알고리즘 기초] 이진 탐색과 시간 복잡도 (3장/ 1105)

- 독학 교재: <알고리즘 첫걸음 C&자바 편>

시간복잡도 부분은 Udemy <자바스크립트 알고리즘 & 자료구조> 강의도 참고하였다.

보통 알고리즘 책은 Big O 표기법을 설명하면서 시간복잡도를 가장 먼저 설명하는데, 이 책에서는 3장에 나왔다.

선형 검색과 이진 검색을 먼저 배운 뒤 둘의 시간복잡도를 비교하는 방식이라 알기 쉬웠다.

---

이진 검색(binary search)

정렬된 배열에서 원하는 데이터를 찾는 알고리즘. 선형 탐색은 배열이 정렬되어 있지 않아도 사용 가능한 알고리즘이었다. 이진 검색은 오름차순으로 정렬된 배열을 대상으로 설명한다.

이진 검색 알고리즘의 개요

1. 검색 대상 배열의 중앙 요소를 확인하여 아래 중 하나를 실행
   (A) 찾는 값과 같다면, 인덱스를 표시하고 종료
   (B) 찾는 값보다 크다면, 검색 대상을 앞쪽으로 한정하여 좁힘
   (C) 찾는 값보다 작다면, 검색 대상을 뒤쪽으로 좁힘
2. B 또는 C의 경우 검색 대상이 없어질 때까지 1을 반복

이진 검색에 필요한 변수

• 검색 대상 배열 a, 찾아낼 값이 저장된 변수 x, 찾은 요소의 인덱스를 저장하는 변수 pos가 필요(초깃값 -1)
• 검색 대상 왼쪽 끝 요소의 인덱스를 저장한 변수 left, 오른쪽 끝 요소의 인덱스를 저장한 변수 right, 배열 중앙 요소의 인덱스를 저장할 변수 middle이 필요
• left의 초깃값은 배열 요소의 첫 번째 인덱스, right의 초깃값은 배열 요소의 마지막 인덱스.

 

배열의 중앙 값 구하기(middle) - 정수형 계산이므로 소수점 아래는 버림

middle = (left + right) / 2

 

변수를 사용한 이진 검색 알고리즘의 개요 설명

1. pos를  -1로 초기화
2. left를 0으로 초기화
3. right를 9로 초기화
4. left와 right로 middle 구하기
5. a[middle]과 구할 값 x를 비교해, 다음 중 하나를 수행
   (A) a[middle] = x라면, pos = middle
   (B) a[middle] > x라면, right = middle-1 하고 검색 대상을 앞쪽으로 좁힘(한정)
   (C) a[middle] < x라면, left = middle+1 하고 검색 대상 뒤쪽으로 좁힘
6. B 또는 C일 경우 원하는 값이 발견되지 않았고, 검색 대상이 남아있으면 처리 반복

 

이진 검색 알고리즘 구현(자바)

- 이진 검색의 반복은 루프 카운터를 사용하지 않고 조건만 지정하므로, for()이 아닌 while()을 사용한다!

- pos가 -1이고(찾는 수를 찾지 못했고), 동시에 left <= right이면(탐색 대상이 남아 있으면) 반복하는 것.

public class BinarySearch {
    public static void main(String[] args) throws IOException {

        int[] arr = {2, 4, 12, 33, 43, 58, 62, 89, 100, 124, 195};
        System.out.print("찾을 값을 입력하세요: ");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());

        int pos = -1;
        int left = 0;
        int right = arr.length - 1; // 인덱스이므로 -1
        int middle = 0;

        while(pos == -1 && left <= right) {
            middle = (left + right) / 2;
            if(arr[middle] == x) {
                pos = middle;
            } else if(arr[middle] > x) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        System.out.printf("pos: %d\n", pos);
    }
}

 

시간 복잡도

- 알고리즘의 효율성을 나타내는 방법 중 하나. 어떤 function()의 입력값이 증가하는 것과 그 실행시간이 변하는 관계에 대해 설명하는 방식.

• 여러 방식 중 여기서는 N개의 데이터를 처리하는 최대 처리 횟수를 식으로 나타내는 방식을 사용.

Big-O 표기법의 특징

- 입력 크기와 실행시간의 관계만 따진다. 최소 수행횟수, 평균 수행횟수, 최대 수행횟수가 있지만 이 중 보통 최대 수행회수를 비교하는 Big-O 표기법(Big-O notation)을 사용함.

- Big-O 표기법에서는 차수만 따지고, 계수는 생략한다. 예를 들어 3N²+2N의 경우 시간복잡도는 O(N²)가 된다.

- Big-O의 시간복잡도는 세분화하면 7가지 경우가 있는데, 효율적인 순서대로 나열하면 아래와 같다.

  O(1) > O(log n) > O(n) > O(n · log n) > O(n² ) > O(2ⁿ) > O(n!)

  경우에 따라 다르겠지만 보통 O(N²) 이상을 넘기지 않는 게 좋다.

선형 검색과 이진 검색의 시간복잡도 비교 

- 선형 검색의 시간복잡도는 O(N)이다. 분할을 실시하지 않으므로 단순히 N회 반복하기 때문.

- 이진 검색의 시간복잡도는 O(log₂N)이다. log₂N은 N개의 데이터를 계속 분할해, 하나의 데이터가 될 때까지 처리한 횟수를 말한다.

정렬(sort)의 시간복잡도 비교

- 버블 정렬, 선택 정렬, 삽입 정렬: O(N²)

- 병합 정렬과 퀵 정렬: O(log₂N²)

 *병합 정렬과 퀵 정렬은 분할을 N회 반복해서, log₂N * N이 되어 O(log₂N²)의 시간복잡도를 가진다.

 

cf. 공간복잡도(auxiliary space complexity)

프로그램을 실행시킨 후 완료하기까지 필요로 하는 자원 공간의 양을 말함. 즉 알고리즘 자체가 필요로 하는 공간을 말한다. 

 

레퍼런스

happycoders/ Big O Notation and Time Complexity

시간복잡도에 대해 자세히 알고 싶을 경우, 아래 사이트에 정말 자세하게 설명이 잘 되어 있으니 추천한다.(영문)

https://www.happycoders.eu/algorithms/big-o-notation-time-complexity/

Big O Notation and Time Complexity - Easily Explained