Big-O 표기법 파악하기

Mar 09, 2024

Published byJynn

999

Big O Notation

빅오(Big-O) 표기법은 알고리즘의 시간복잡도 및 공간복잡도를 추정하고 비교하는데 사용되는 주요 개념입니다. 이것은 알고리즘의 실행 시간과 필요한 메모리 사용량이 입력 데이터 크기에 따라 어떤 패턴으로 변하는지 보여줍니다.

빅오 표기법을 사용하면, 알고리즘의 효율성을 이해하고, 다양한 알고리즘들의 성능을 비교하는 것이 가능해집니다. 이 접근법을 이해하고 사용하면 알고리즘의 성능 이해에 큰 도움이 될 것입니다.

Understanding Big O Notation

알고리즘의 성능을 확인하기 위한 전통적인 방법으로 실행 시간을 측정하거나 연산 횟수를 세는 방법이 있지만, 이들은 알고리즘의 복잡도를 완전히 이해하거나 비교하는 데 한계가 있습니다:

함수 시간 측정의 한계: 실행 시간은 여러 외부 요인에 따라 달라질 수 있습니다. 이로 인해 컴퓨터의 성능이나 CPU 작업량 등으로 인한 본질적인 성능 왜곡이 발생할 수 있습니다.
연산 횟수 측정의 한계: 개별 연산의 횟수를 세는 것은 오류를 유발하기 쉬우며, 이는 상당히 번거로운 작업입니다. 더욱이, 이 접근법은 알고리즘의 전체적인 효율성이 아닌 세부적인 수행 과정에 대한 분석에 초점을 맞춰, 알고리즘의 성능을 전체적으로 이해하는 데 한계가 있습니다.

이러한 한계를 극복하고, 알고리즘 복잡도를 공정하게 비교하고 이해하는 방법으로 빅오 표기법이 일반적으로 사용됩니다.

Asymptotic Notation

점근 표기법(Asymptotic Notation)은 일반적으로 알고리즘의 복잡도를 측정하는데 사용됩니다. 특히, 이 표기법은 입력 크기가 무한대에 가까워지는 상황에서 알고리즘의 성능 변화를 설명하는 데 가장 효과적입니다.

점근 표기법에는 몇 가지 일반적인 형태가 있습니다:

빅-오 표기법(Big-O Notation): 이 표기법은 알고리즘의 최악의 상황에서의 성능을 설명합니다. 알고리즘의 성능을 평가할 때 가장 널리 사용됩니다.
빅-오메가 표기법(Big-Omega Notation): 이 표기법은 알고리즘의 최적의 상황에서의 성능을 설명합니다. 즉, 알고리즘이 이론적으로 얼마나 잘 수행될 수 있는지를 보여줍니다.
빅-세타 표기법(Big-Theta Notation): 이 표기법은 알고리즘의 평균적인 상황에서의 성능을 설명합니다. 알고리즘의 전반적인 성능을 간략하게 이해하는 데 유용합니다.

이 외에도 다양한 점근 표기법들이 존재하지만, 다음과 같은 장점들 때문에 빅오 표기법이 가장 보편화되어 있습니다:

단순화: 복잡한 수학적 표현을 간결하게 변환하여, 알고리즘의 복잡도를 쉽게 이해하고 비교 가능하게 합니다.
성능 분석: 입력 데이터의 크기가 증가할 때, 알고리즘이 어떻게 반응하는지 직관적으로 파악하게 해줍니다. 이는 성능 변화를 예측하고 이해하는 데 도움이 됩니다.
비교 기준 제공: 서로 다른 알고리즘들의 성능을 일관된 기준으로 공정하게 비교할 수 있게 합니다.

Simplifying Expressions

빅오 표기법은 알고리즘 입력의 크기와 복잡도 사이의 관계에 대한 전반적인 흐름을 파악하는데 주목합니다. 그래서, 결과에 크게 영향을 미치지 않는 부분은 모두 제거하여 표현을 단순화합니다.

예를 들어, 어떤 한 알고리즘이 2ⁿ + n²의 복잡도를 가진다고 가정하겠습니다. 여기서 n의 입력값이 커짐에 따라 2ⁿ의 증가률은 n²과 비교했을때 어마어마한 차이를 보입니다. n = 64 라고 한다면, 64² = 4,096 이지만 2⁶⁴ = 18,446,744,073,709,551,616 라는 읽기도 어려운 결과가 계산됩니다.

# n = 2
n² -> 2² = 4
2ⁿ -> 2² = 4

# n = 64
n² -> 64² = 4096
2ⁿ -> 2⁶⁴ = 18446744073709551616

이런 이유로, 2ⁿ + n²에서 n²이 미치는 영향은 미미하기 때문에 최고차항인 2ⁿ만 남겨놓고 다른 부가적인 부분은 모두 제거합니다.

⛔ O(100)           -->   ✅ O(1)
⛔ O(2n)            -->   ✅ O(n)
⛔ O(5n²)           -->   ✅ O(n²)
⛔ O(n + 10)        -->   ✅ O(n)
⛔ O(2n + 10)       -->   ✅ O(n)   
⛔ O(5n² + 2n + 8)  -->   ✅ O(n²)
⛔ O(2ⁿ + 2n² + 8)  -->   ✅ O(2ⁿ)

Algorithmic Complexity

복잡도(Complexity)란 수학과 컴퓨터 과학에서 작업 완료에 필요한 자원을 측정하는 방법입니다. 알고리즘이나 시스템의 성능을 측정하기 위해 주로 사용되는 개념입니다. 복잡도를 파악하는 것은 해당 알고리즘 또는 시스템이 어느 정도의 성능을 내는지, 어떤 유형의 작업에 가장 적합한지 결정하는 데 중요한 요소입니다.

자원의 종류:
- 자원이란 어떤 작업을 수행하는데 사용되는 계산 자원을 말하며, 이로 인해 복잡도가 결정됩니다.
- 이 자원은 주로 시간(계산 시간)과 공간(메모리 사용량)이라는 두 가지 형태를 가집니다.
- 복잡도 측정에는 시간 및 공간이라는 자원을 단독으로 사용하거나, 동시에 고려할 수 있습니다.
- 자원을 종종 비용(Cost)이라고 표현하기도 합니다.
- 자원의 사용량이 적을수록, 즉 비용이 낮을수록 핵심 계산 작업이 더 효율적으로 수행됩니다.
가독성과 복잡도:
- 코드의 복잡도와 가독성은 서로 상충하는 성질을 가질 수 있습니다.
- 예를 들어, 한 줄로 간결하게 작성된 코드는 매우 복잡한 계산을 수행할 수 있지만, 그 복잡도 때문에 코드를 이해하는 데 어려움을 겪을 수 있습니다.
복잡도와 최적화:
- 알고리즘의 복잡도를 최적화한다는 것은 해당 알고리즘의 성능을 향상시키는 것을 의미합니다.
- 이는 주로 사용된 자원의 양을 최소화하는 형태로 이루어지며, 시간과 메모리 등 다양한 자원이 이에 해당할 수 있습니다.
- 어떤 종류의 복잡도가 최적화의 주요 목표가 되는지는 특정 문제의 요구사항과 주어진 자원에 따라 달라집니다. 어떤 경우에는 계산 시간을 줄이는 것이 최우선 목표일 수 있으며, 다른 경우에는 메모리 사용량을 최소화하는 것이 중요할 수 있습니다.

Complexity Classes

복잡도 클래스(Complexity Classes)는 계산 복잡도 이론에서 사용하는 추상적인 계산 문제 또는 알고리즘의 분류 체계입니다. 이들 클래스는 시간이나 공간과 같은 계산 자원의 측정 기준에 따라 결정되며, 해당 클래스에 속하는 모든 문제 또는 알고리즘들이 공유하는 주요 계산적 성질을 정의합니다.

이에 해당하는 복잡도 클래스는 여러 가지가 있지만, 아래에서는 특히 빅오 표기법으로 측정되는 시간 복잡도를 중점으로 살펴보겠습니다:

O(1) - 상수 시간(Constant Time):
- 이 클래스에 속하는 알고리즘은 입력 데이터의 크기와 상관없이 일정한 시간이 걸립니다.
- 배열의 특정 요소에 접근하거나, 변수의 값을 증가시키는 등의 간단한 연산이 해당됩니다.
O(log n) - 로그 시간(Logarithmic Time):
- 로그 시간 복잡도를 가진 알고리즘은 데이터 크기가 증가함에 따라 필요한 작업 시간이 로그 함수적으로 증가합니다.
- 이진 탐색(Binary Search)이나 이진 트리(Binary Tree) 작업이 대표적인 예시입니다.
O(n) - 선형 시간(Linear Time):
- 데이터 크기에 비례하여 작업 시간이 증가하는 알고리즘입니다.
- 예를 들어, 단일 반복문(Single Loop)을 통해 배열의 모든 요소를 순회하는 경우가 이에 해당합니다.
O(n log n) - 로그 선형 시간(Log Linear Time):
- 입력의 크기 n에 대해 O(n log n)의 시간이 걸리는 알고리즘입니다.
- 대부분의 효율적인 정렬 알고리즘들이 이 범주에 속합니다.
- 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)과 같은 알고리즘이 이 복잡도를 가집니다.
O(n^2) - 이차 시간(Quadratic Time):
- 입력의 크기의 제곱에 비례해서 시간이 증가합니다.
- 이중 반복 문법을 사용하는 알고리즘들이 이 복잡도를 가집니다.
- 버블 정렬(Bubble Sort)이나 삽입 정렬(Insertion Sort)과 같은 알고리즘이 이 클래스에 속합니다.
O(2^n) - 지수 시간(Exponential Time):
- 입력의 크기에 따라 시간 복잡도가 급격하게 증가합니다.
- 가장 비효율적인 알고리즘으로, 주로 컴퓨팅 자원을 많이 사용하는 문제를 해결할 때 사용되며, 가능한 한 피하는 것이 좋습니다.
- 재귀적으로 모든 가능한 해결책을 생성하고 탐색하는 알고리즘이 여기에 해당됩니다.
O(n!) - 팩토리얼 시간(Factorial Time):
- 항목의 모든 가능한 순열을 생성하고 검사해야 할 때 해당됩니다.
- 예를 들어, 완전 탐색(Brute-Force) 알고리즘이 이에 해당됩니다.

각 복잡도 클래스는 문제 크기에 따라 필요한 계산 작업량이 어떻게 증가하는지 나타냅니다. 이 정보는 알고리즘을 선택하거나 설계할 때 매우 중요한 기준이 됩니다. 즉, 특정 문제에 대해 어떤 알고리즘을 적용할 것인지, 그리고 그 알고리즘의 성능이 어떻게 되는지를 예측하는 데 도움이 됩니다.

Time Complexity

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 필요한 연산의 횟수를 나타냅니다. 일반적으로, 이 연산 횟수는 입력 데이터 크기에 비례하게 됩니다.

실제 프로그램에서 실행 시간은 단순히 코드의 행 수에 의해 결정되지 않습니다. 알고리즘 내에서 발생하는 연산의 수가 그 중요한 키입니다. 이 수는 입력되는 데이터의 양에 따라 증가합니다.

이해를 돕기 위해, 팩토리얼을 계산하는 재귀 함수를 예로 들어 시간 복잡도를 분석해 보겠습니다:

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

이 함수는 숫자 n에 대해 팩토리얼을 계산하는 재귀 함수입니다. n이 0인지 확인 후, 0이 아닐 경우 n과 factorial(n - 1)의 곱을 반환합니다. 함수가 n번 재귀 호출될 때마다 하나의 연산이 수행됩니다. 따라서 이 함수의 시간 복잡도는 O(n)입니다.

즉, 선형 시간 복잡도 O(n)을 가진 알고리즘은 입력 크기에 비례하여 연산 횟수가 증가합니다. 이러한 점은 이 함수가 큰 데이터 셋에 대해 동작할 때, 시간 효율성에 제한이 있다는 것을 시사합니다. 때문에 높은 효율성이 요구되는 상황에서는, 다른 접근 방법 또는 최적화된 알고리즘이 고려될 수 있습니다.

이와 같이, 시간 복잡도를 이해하고 계산하는 것은 특정 연산을 수행하는 데 얼마나 많은 시간이 소요될지 예측하는 데 도움이 됩니다. 이는 효율적인 알고리즘을 만들고 성능상의 문제를 해결하는데 중요한 역할을 합니다.

Space Complexity

공간 복잡도(Space Complexity)는 알고리즘이 문제를 해결하는 데 필요한 메모리 또는 저장 공간의 양을 의미합니다. 이는 프로그램의 매개변수, 호출 스택, 전역 변수 등에 의해 결정되며, 프로그램 실행 도중 필요한 메모리의 총량을 나타냅니다.

공간 복잡도를 판단하기 위한 계산법은 여러 가지가 있지만, 일반적으로 입력 데이터의 크기에 따라 필요한 공간의 양을 간략하게 나타낼 수 있는 빅오 표기법이 가장 널리 사용됩니다.

아래에 제시된 두 가지 팩토리얼 계산 알고리즘 예제를 통해, 공간 복잡도가 어떻게 달라질 수 있는지 살펴보겠습니다.

먼저, 재귀를 사용한 팩토리얼 계산 함수는 자신이 다시 호출될 때마다 시스템 콜 스택에 새로운 프레임을 추가합니다. n 팩토리얼을 계산하려면 n개의 스택 프레임이 콜 스택에 추가되어야 하므로 공간 복잡도는 O(n)이 됩니다.

public static int recursiveFactorial(int n) {
    if (n == 0) return 1;
    else return recursiveFactorial(n - 1) * n;
}

반면, 반복문을 사용하여 팩토리얼 계산 함수를 구현하면, 이 알고리즘이 필요로 하는 추가적인 메모리 공간이 입력 n의 크기와 관계없이 result라는 단일 정수 변수 하나만 있기 때문에, 공간 복잡도는 O(1)로 간주될 수 있습니다.

private static int iterativeFactorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

공간 복잡도를 파악하는 것은 프로그램이 필요로 하는 전체 메모리 또는 저장 공간의 양을 이해하고 최적화 하는데 중요한 단계입니다. 메모리 사용량을 최소화하는 알고리즘은 자원 제한이 엄격한 환경에서는 특히 중요하며, 프로그램의 전체 성능 개선에도 기여할 수 있습니다.

📚 알고리즘 문제 해결 전략
📺 그림으로 쉽게 배우는 자료구조와 알고리즘
📺 JavaScript Algorithms and Data Structures Masterclass
🔗 freeCodeCamp.org
🔗 bigocheatsheet.com

Algorithm