들어가며

시간 복잡도(Time Complexity)란 특정 알고리즘이 문제를 해결하는데 걸리는 시간을 의미하고,
통상적으로 최악의 경우(빅오, ‘O’)를 구해서 표기합니다

 

이전 포스팅 에서 시간복잡도에 대해 알아보았는데요,
이번 포스팅에서는 순차탐색과 이진탐색에 대하여 알아보고
간단한 leetcode (릿코드) 예제와 함께 시간복잡도를 계산해 보도록 하겠습니다


Leetcode 문제 이해하기

Search Insert Position - LeetCode ‘EASY’ 난이도인 문제입니다

이진탐색을 공부하기에 좋은 예제라 생각하여 가져왔습니다 👀

  • 배열의 인덱스는 0부터 시작합니다
  • 오름차순으로 정렬된 array와, 타겟이 Input으로 제공됩니다
  • Output으로 타겟이 위치할 인덱스 위치를 return 하여 줍니다

1번 예제에서는 목표값 '5'가 배열에서 2에 위치한 것을 알 수 있습니다

4번 예제에서는 목표값 '0'이 배열에서 0번째 위치해야 하는 것을 알 수 있습니다


순차탐색 풀이 & 시간복잡도

순차 탐색의 경우, 처음부터 비교하여 비교가 끝날때까지 차례로 훑어보게 됩니다

  • Example1, 목표값 5 에서는 탐색 3번 [1, 3, 5]
  • Example2, 목표값 2 에서는 탐색 2번 [1, 3]
  • Example3, 목표값 7 에서는 탐색 4번 [1, 3, 5, 6]
  • Example4, 목표값 0 에서는 탐색 1번 [1]
  • Example5, 목표값 0 에서는 탐색 1번 [1]

최악의 경우 마지막 끝까지 4번 훑어보게 됩니다.

public int searchInsert(int[] nums, int target) {
    int length = nums.length;
    for (int i = 0; i < length; i++) {
        if (nums[i] == target) {
            return i;
        }

        if (target < nums[i]) {
            return i;
        }
    }
    return length;
}

즉, 최악의 경우인 n번까지 훑어보게 됨으로 시간복잡도는 O(n)을 가지게 됩니다.


이진탐색 풀이 & 시간복잡도

이진탐색의 경우 업&앤 다운으로 숫자맞추기를 한다고 보면 됩니다.

“1부터 100까지 숫자가 정렬되어 있을때 내가 생각하고 있는 숫자를 맞춰봐” (답은 43)
50 땡! -> 다운
25 땡 -> 업
36 땡 -> 업
43 정답

만약 순차탐색으로 숫자를 맞추게 된다면 1부터 43까지 차례로 확인을 하겠죠?

그러나 이진탐색은 위와 같이 4번의 질의로 정답을 맞추었습니다.

 

즉, 이진탐색은 순차탐색보다 효율적으로 숫자를 탐색하고 있습니다.

마찬가지로 leetcode 문제를 살펴보겠습니다

 

  • Example1, 목표값 5 에서는 탐색 1번 [5]
  • Example2, 목표값 2 에서는 탐색 2번 [3, 1]
  • Example3, 목표값 7 에서는 탐색 3번 [3, 5, 6]
  • Example4, 목표값 0 에서는 탐색 2번  [3, 1]
  • Example5, 목표값 0 에서는 탐색 1번  [1] 
public static int searchInsert(int[] nums, int target) {
    int first = 0;
    int last = nums.length - 1;

    while (first <= last) {
        int mid = (first + last) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
    return first;
}

이진탐색에서는 중앙값과 목표값을 비교하여 인덱스의 위치를 계속 조절하고 있습니다!!

이제 이진탐색의 시간복잡도를 구해보도록 하겠습니다.

  • 먼저 숫자 N이 주어집니다
  • 첫 탐색을 하게 되면 N/2 만큼 남게됩니다
  • 두번째 탐색을 하게 되면 1/2 * N/2 만큼 남게 됩니다
  • 세번째 탐색을 하게 되면 1/2 * 1/2 * N/2 만큼 남게 됩니다
  • k번째 탐색을 하게 된다면 (1/2)^k * N 만큼 남게됩니다
  • ‘(1/2)^k * N = 1’ 이 성립하기에 양변에 2^k을 곱하여 줍니다
  • N = 2^k가 되어 k 값을 구하게 되면 k = log2N 이 됩니다

시간복잡도는 상수를 제거하여 표현하기에 이진탐색의 시간복잡도는 logN으로 표현할 수 있습니다

주의, 이진탐색의 경우 숫자가 정렬되어 있어야 합니다 (오름차순, 내림차순)


출처

Search Insert Position - LeetCode
이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)

블로그 이미지

yhmane

댓글을 달아 주세요