배열 교집합 계산: 알고리즘 분석과 Big-O 시간 복잡도

두 배열의 교집합을 구하는 알고리즘을 분석하고, Big-O 표기법을 통해 시간 복잡도를 알아보겠습니다.

 

 

목차

 

 

 

배열 교집합 계산: 알고리즘 분석과 Big-O 시간 복잡도

두 배열의 교집합을 구하는 예제 코드를 분석하고, Big-O 표기법을 통해 시간 복잡도를 알아보겠습니다.

 

int intersection(int[] a, int[] b) {
    mergesort(b);
    int intersect = 0;
    for (int x : a) {
        if (binarySearch(b, x) >= 0) {
            intersect++;
        }
    }
    return intersect;
}

 

이 함수는 두 개의 배열 a와 b에서 공통으로 등장하는 요소의 개수를 계산하는 함수입니다. 즉, a와 b의 교집합의 크기를 반환합니다.

 

함수의 동작 방식

• mergesort(b): 우선, 배열 b를 병합 정렬(mergesort) 알고리즘을 이용해 정렬합니다. 병합 정렬은 일반적으로 O(n log n)의 시간 복잡도를 가집니다.
• for (int x : a): 배열 a의 모든 요소에 대해 반복합니다.
• binarySearch(b, x): a의 각 요소 x가 정렬된 배열 b에 존재하는지를 이진 탐색(binary search)을 통해 확인합니다. 이진 탐색은 O(log n)의 시간 복잡도를 가집니다.
• intersect++: 이진 탐색의 결과로 x가 b에 존재하는 경우, 교집합 크기를 나타내는 intersect 값을 1 증가시킵니다.
• return intersect: 최종적으로 a와 b의 교집합 크기, 즉 intersect 값을 반환합니다.

 

수행 시간(Big-O 표기법)

이제 이 함수의 전체 수행 시간을 Big-O 표기법으로 분석해보겠습니다.

• mergesort(b)
  • 병합 정렬의 시간 복잡도는 O(m log m)입니다. 여기서 m은 배열 b의 길이입니다.
• for (int x : a)
  • 이 루프는 배열 a의 모든 요소에 대해 실행됩니다. 배열 a의 길이를 n이라고 할 때, 루프 자체는 O(n)입니다.
  • 루프 내부에서 binarySearch(b, x)가 호출됩니다. 이진 탐색의 시간 복잡도는 O(log m)입니다. 이진 탐색은 배열 b의 크기인 m에 대해 로그 시간(logarithmic time)을 가집니다.

따라서 루프 내의 binarySearch(b, x)를 포함한 전체 루프의 시간 복잡도는 O(n * log m)입니다.

 

최종 시간 복잡도

함수의 전체 수행 시간은 다음 두 가지 주요 부분의 수행 시간을 합한 것입니다:

• 병합 정렬: O(m log m)
• 배열 a에 대해 루프를 돌며 이진 탐색을 수행: O(n * log m)

 

따라서 이 함수의 최종 시간 복잡도는 O(m log m + n log m)입니다.

 

이 시간 복잡도는 m과 n의 상대적인 크기에 따라 영향을 받을 수 있습니다. 하지만 가장 시간이 많이 걸리는 부분이 m log m 또는 n log m 둘 중 하나가 될 것이므로, 이 함수는 두 배열의 크기에 따라 효율성이 결정됩니다.

 

만약 두 배열의 크기가 매우 다른 경우, 예를 들어 m이 매우 작고 n이 매우 큰 경우, O(n log m)이 전체 수행 시간을 지배하게 될 것입니다. 반대로 두 배열이 거의 같은 크기라면 두 항목이 비슷하게 수행 시간을 차지하게 됩니다.