Big O란?

목차

Big O 표기법 완벽 정리

알고리즘을 배우는 개발자라면 Big O 표기법을 반드시 알아야 합니다. Big O는 알고리즘의 효율성을 평가하는 핵심 도구로, 시간 복잡도와 공간 복잡도를 분석합니다. 

---

1. Big O 란? 

✅ Big O표기법의 기본 개념

Big O 표기법은 알고리즘의 성능을 분석하는 기법으로, 입력 크기(n) 에 따라 실행 시간과 메모리 사용량이 어떻게 변하는지를 설명해 줍니다.

• 시간 복잡도(Time Complexity): 알고리즘이 실행되는 데 걸리는 시간의 증가율을 나타냄.
• 공간 복잡도(Space Complexity): 알고리즘이 실행될 때 필요한 메모리의 증가율을 나타냄.
• 점근적 분석: nnn이 무한히 커질 때의 성능을 기준으로 평가.

 

public int addNumbers(int a, int b) {
    return a + b;
}

• 시간 복잡도: O(1) (항상 일정한 연산 수행)
• 공간 복잡도: O(1) (추가 메모리 사용 없음)

 

✅ Big O의 특징

Big O 표기법은 입력 크기에 따른 알고리즘의 수행 시간을 최악의 경우(Worst Case) 기준으로 표현합니다.

 

🔹 주요 시간 복잡도 종류

Big O 표기	명칭	예시
O(1)	상수 시간	배열에서 특정 인덱스 값 조회
O(log n)	로그 시간	이진 탐색(Binary Search)
O(n)	선형 시간	배열의 모든 요소 순회
O(n log n)	선형 로그 시간	병합 정렬(Merge Sort)
O(n²)	이차 시간	버블 정렬(Bubble Sort)
O(2ⁿ)	지수 시간	피보나치 수열(재귀)
O(n!)	팩토리얼 시간	외판원 문제(Brute Force)

 

특징 요약

• 빅오 표기법은 상수 계수를 무시: O(2n)과 O(n)은 동일하게 O(n)으로 표현됨
• 입력 크기(n)가 커질수록 더 큰 차이가 발생
• 최악의 경우(Worst Case)를 기준으로 계산

 

✅ 장점과 단점

• 장점:
  • 알고리즘 효율성 비교 용이.
  • 대규모 데이터에서 확장성 예측 가능.
• 단점:
  • 실제 실행 시간(상수 시간) 미반영.
  • 작은 입력에서는 차이 미미.

---

2. 시간 복잡도(Time Complexity) 

2.1. O(1) - 상수 시간 (Constant Time)

 

public int getFirstElement(int[] arr) {
    return arr[0];
}

• 배열의 첫 번째 요소를 반환하는 코드입니다.
• 배열 크기가 커져도 항상 한 번만 연산하므로 O(1)입니다.

✅ 시간 복잡도: O(1)
✅ 공간 복잡도: O(1)

 

📌 예시:

• 전화번호부에서 첫 번째 연락처를 찾는 것과 유사합니다.

2.2. O(n) - 선형 시간 (Linear Time)

public void printAllElements(int[] arr) {
    for (int num : arr) {
        System.out.println(num);
    }
}

• 배열의 모든 요소를 출력하는 코드입니다.
• 배열 크기(n)에 따라 실행 시간이 비례적으로 증가합니다.

✅ 시간 복잡도: O(n)
✅ 공간 복잡도: O(1)

 

📌 예시:

• 한 줄로 선 사람들을 차례대로 확인하는 것과 같습니다.

2.3. O(log n) - 로그 시간 (Logarithmic Time)

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    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;
}

• 이진 탐색(Binary Search) 을 이용해 정렬된 배열에서 원하는 값을 찾습니다.
• 검색 범위를 절반으로 줄이기 때문에 O(log n)입니다.

✅ 시간 복잡도: O(log n)
✅ 공간 복잡도: O(1)

 

📌 예시:

• 전화번호부에서 특정 사람을 찾을 때, 한 페이지씩 넘기는 것이 아니라 절반씩 줄여가는 방식과 같습니다.

2.4. O(n²) - 이차 시간 (Quadratic Time)

public 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;
            }
        }
    }
}

• 버블 정렬(Bubble Sort) 은 두 개씩 비교하며 정렬하는 방식입니다.
• 중첩된 반복문 으로 인해 실행 시간이 n²에 비례합니다.

✅ 시간 복잡도: O(n²)
✅ 공간 복잡도: O(1)

 

📌 예시:

• 학생들의 키를 비교하며 하나씩 정렬하는 과정과 같습니다.

---

3. 공간 복잡도(Space Complexity) 

공간 복잡도는 알고리즘이 사용하는 추가적인 메모리 공간 을 의미합니다.

3.1. O(1) - 상수 공간

public int sum(int a, int b) {
    return a + b;
}

• 변수를 2개만 사용하므로 추가적인 공간 사용이 없습니다.

✅ 공간 복잡도: O(1)

3.2. O(n) - 선형 공간 (재귀 함수 예제)

public int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

• 재귀 호출이 스택(stack) 을 사용하므로, O(n)만큼의 공간이 필요합니다.

✅ 공간 복잡도: O(n)

3.3. 배열을 이용한 공간 복잡도

public int[] copyArray(int[] arr) {
    int[] newArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

• 새로운 배열을 생성하는 데 O(n)의 공간이 필요합니다.

✅ 공간 복잡도: O(n)

---

4. 시간 복잡도 & 공간 복잡도 비교표

알고리즘	시간 복잡도	공간 복잡도
상수 연산 (O(1))	O(1)	O(1)
선형 탐색 (O(n))	O(n)	O(1)
이진 탐색 (O(log n))	O(log n)	O(1)
버블 정렬 (O(n²))	O(n²)	O(1)
재귀 (O(n))	O(n)	O(n)

---

5. Big O 표기법의 주요 사항과 특이사항

주요 사항

• 시간 vs 공간 트레이드오프: 메모리를 더 써서 시간을 줄일 수 있음(예: 해시맵 사용 시 O(1)O(1)O(1) 시간, O(n)O(n)O(n) 공간).
• 입력 데이터 의존: 정렬 여부에 따라 성능 달라짐(이진 탐색은 정렬 필요).
• 실제 성능: 캐시, 병렬 처리 등으로 이론과 다를 수 있음.

특이사항

• 재귀와 공간 복잡도: 재귀 호출은 스택 메모리를 사용하므로 O(n)O(n)O(n) 공간 복잡도가 추가될 수 있음.
• 드롭된 상수: O(3n)=O(n)O(3n) = O(n)O(3n)=O(n)으로 간소화.
• 복잡한 경우: 분할 정복 알고리즘(예: 병합 정렬)은 O(nlogn)O(n log n)O(nlogn)으로 분석.

---

6. 결론

Big O 표기법은 Java 개발자라면 반드시 익혀야 할 핵심 개념입니다. O(n)O(n)O(n), O(n2)O(n^2)O(n2), O(logn)O(log n)O(logn) 같은 기본 패턴부터 시작해 실무에 적용해보세요. 위 Java 예제를 참고하며 연습하면 알고리즘 효율성 분석이 한결 쉬워질 것입니다!

📚 학습 방법:
1️⃣ 자료구조와 알고리즘 개념 익히기
2️⃣ 다양한 코드 예제 직접 작성해 보기
3️⃣ 코딩 테스트 문제를 풀며 Big O 분석 적용하기