빅오 표기법(Big O notation)

빅오 표기법(Big O notation)은 알고리즘의 시간 복잡도나 공간 복잡도를 나타내기 위해 사용되는 수학적 표현 방식이다. 이 표기법은 알고리즘이 입력 데이터에 대해 어떻게 확장되는지를 나타내며, 최악의 경우의 성능을 대략적으로 표현한다.

 

O(1) - 상수 시간

• 설명 : 입력 데이터의 크기와 상관없이 알고리즘의 실행 시간이 일정하다.
• 예시 : 배열에서 특정 인덱스의 요소에 접근하는 경우. 배열의 크기와 관계없이 하나의 연산만으로 원하는 요소를 얻을 수 있다.

int[] array = {1, 2, 3, 4, 5};
int getElement(int index) {
    return array[index];
}

 

 

O(n) - 선형 시간

• 설명 : 입력 데이터의 크기에 비례하여 실행 시간이 증가한다.
• 예시 : 배열의 모든 요소를 순회하는 경우. 배열의 크기가 n일 때, n개의 요소를 모두 확인해야 한다.

void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}

 

 

O(log n) - 로그 시간

• 설명 : 데이터가 두 배로 증가할 때마다 추가적인 작업이 일정하게 증가한다. 이진 탐색이 대표적이다.
• 예시 : 이진 탐색. 정렬된 배열에서 특정 값의 위치를 찾을 때, 배열을 반으로 나누어가며 탐색 범위를 줄여간다.

int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

 

한 번 연산할 때마다 연산의 범위가 반씩 줄어드는 경우에 위와 같이 되는 것을 확인할 수 있다.

 

 

O(n log n) - 선형 로그 시간

• 설명 : 데이터의 양이 두 배로 증가할 때, 실행 시간이 그보다 조금 더 많이 증가한다. 많은 효율적인 정렬 알고리즘이 이 범주에 속한다.
• 예시: 병합 정렬. 데이터를 분할하고, 각 부분을 정렬한 다음 합치는 과정을 포함한다.

void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

 

 

O(n^2) - 이차 시간

• 설명 : 입력 데이터의 크기에 비례하여 실행 시간이 제곱으로 증가한다.
• 예시 : 버블 정렬 같은 기본적인 정렬 알고리즘. 각 요소를 다른 모든 요소와 비교한다. 흔히 이중 for 문이라고 이해하면 쉽다.

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]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
}