빅오 표기법 (Big-O notation)

빅오 표기법(Big-O Notation)은 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 수학적 기법으로, 알고리즘의 성능을 분석할 때 사용됩니다.

 

주로 입력 크기(n)가 커질 때 알고리즘의 성능이 어떻게 변화하는지 나타내고, 최악의 경우 시간 복잡도를 기준으로 표기

1. O(1): 상수 시간 복잡도. 입력 크기와 상관없이 실행 시간이 일정
2. O(n): 선형 시간 복잡도. 입력 크기(n)가 커질수록 실행 시간이 비례하여 증가
3. O(n^2): 이차 시간 복잡도. 입력 크기(n)가 커질수록 실행 시간이 n의 제곱에 비례하여 증가
4. O(log n): 로그 시간 복잡도. 입력 크기(n)가 커져도 실행 시간은 상대적으로 적게 증가
5. O(n log n): 로그 선형 시간 복잡도. 일반적으로 효율적인 알고리즘에서 발생

---

O(1)

int getFirstElement(int arr[]) {
    return arr[0];  //입력 크기와 관계없이 일정한 시간에 실행
}

 

 

---

O(n)

int sumArray(int arr[], int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i]; 	 //배열을 한 번 순회하며 합 계산
    }
    return sum;
}

---

O(n²)

void printPairs(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("(%d, %d) ", arr[i], arr[j]);   //2중 for문으로 모든 쌍 출력
        }
    }
}

---

O(log n)

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;       //타겟 찾으면 해당 인덱스 반환
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;  //타겟 없으면 -1 반환
}

---

O(n log n)

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int leftArr[n1], rightArr[n2];
    
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        rightArr[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

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

---