시간 복잡도

우리는 알고리즘 문제를 풀때마다 어떻게 효율적으로 코드를 짤 것인지 생각한다.
이것은 효율적으로 알고리즘을 짠다는 것은 시간 복잡도를 고민하는 것과 같다.

• 효율적인 알고리즘을 구현하는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 '최소화'하겠다는 것을 말한다.

Big-O 표기법

시간 복잡도는 다음과 같은 순서로 나열된다. 아래 순서는 시간 복잡도가 작은 것부터 큰 것으로 나열한 것이다.

-- 코드 문제가 있어 Ctrl+c해서 웹 IDE에 붙여넣는 것 추천
온라인IDE

1. O(1)(상수 시간) : 입력 크기에 상관없이 그대로 출력이 되는 것을 말한다.
ex) 배열을 출력할 때

public class Main {
    public static void main(String[] args) {
        // 배열 생성
        int[] array = {1, 2, 3, 4, 5};

        // 배열 값 출력
        System.out.println("배열 값 출력:");
        for (int i = 0; i < array.length; i++) {
            System.out.println("Index " + i + ": " + array[i]);
        }
    }
}

2. O(log n)(로그 시간) : 입력 크기에 대해 로그 함수의 시간이 걸리는 경우이다. 이진탐색과 같은 알고리즘이 이에 해당한다.

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15, 17};
        int target = 7;

        // Arrays.binarySearch() 호출
        int result = Arrays.binarySearch(array, target);

        if (result >= 0) {
            System.out.println("요소 " + target + "을(를) 찾았습니다. 인덱스: " + result);
        } else {
            System.out.println("요소 " + target + "을(를) 찾을 수 없습니다.");
        }
    }
}

3. O(n)(선형시간) : 입력 크기에 비례하여 실행 시간이 증가하는 경우이다. 배열이나 리스트의 요소를 한 번 탐색하는 것이 O(n)이다.

public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        
        // 배열의 각 요소를 출력
        for (int i = 0; i < array.length; i++) {
            System.out.println("Index " + i + ": " + array[i]);
        }
    }
}

• 만약 for문을 2번 사용한다면 O(2*n)이다.

4. O(n log n) : 일부 정렬 알고리즘이 이에 해당한다. 퀵 정렬과 병합 정렬이 그 예시이다.

(1) 퀵 정렬

import java.util.Arrays;

public class QuickSort {
    // 퀵 정렬 메소드
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 파티션 분할
            int pivotIndex = partition(arr, low, high);
            
            // 분할된 부분에 대해 재귀적으로 퀵 정렬 수행
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 파티션 분할 메소드
    public static int partition(int[] arr, int low, int high) {
        // 피벗 설정 (여기서는 맨 끝 요소를 피벗으로 선택)
        int pivot = arr[high];
        int i = low - 1; // 작은 요소들의 마지막 인덱스

        // 배열을 탐색하면서 피벗보다 작은 요소를 피벗 앞으로 이동
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // arr[i]와 arr[j] 위치 교환
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 피벗과 i+1 위치의 요소 교환 (피벗을 정렬된 위치로 이동)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        // 피벗의 최종 위치를 반환
        return i + 1;
    }

    // 메인 메소드
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        quickSort(arr, 0, n-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

(2) 병합 정렬

import java.util.Arrays;

public class MergeSort {
    // 병합 정렬 메소드
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 중간 지점 계산
            int mid = (left + right) / 2;
            
            // 왼쪽 부분 배열을 정렬
            mergeSort(arr, left, mid);
            // 오른쪽 부분 배열을 정렬
            mergeSort(arr, mid + 1, right);
            
            // 정렬된 부분 배열을 병합
            merge(arr, left, mid, right);
        }
    }

    // 병합 메소드
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // 왼쪽 부분 배열의 크기
        int n2 = right - mid; // 오른쪽 부분 배열의 크기
        
        // 임시 배열 생성
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        // 왼쪽 부분 배열 복사
        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        // 오른쪽 부분 배열 복사
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[mid + 1 + j];
        }

        // 두 부분 배열을 병합
        int i = 0, j = 0;
        int k = left; // 초기 병합 위치
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 남은 요소들 복사
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 메인 메소드
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original array: " + Arrays.toString(arr));
        
        mergeSort(arr, 0, arr.length - 1);
        
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

5. O(n^2) : 이차 시간으로, 입력 크기의 제곱에 비례하여 실행 시간이 증가한다. 이중 for문을 사용하는 버블정렬과 선택, 삽입정렬이 이에 해당한다.

// 버블정렬
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

6. O(n^c)(n의 상수 제곱): c는 2보다 큰 상수이다. 입력 크기에 비례하여 실행 시간이 더 빠르게 증가한다. 행렬의 경우 O(n^3)이다.

7. O(2^n) : 입력 크기에 대해 실행 시간이 지수적으로 증가한다. 사용하지 말하야 할 알고리즘이다.

8. O(n!) : 팩토리얼 시간으로, 실행 시간이 입력 크기의 팩토리얼에 비례하여 증가한다. 역시 매우 비효율적이어서 사용하지 말아야 할 알고리즘이다.