Big O 치트 시트: Python 예제로 설명

알고리즘의 효율성을 평가하고 순위를 매기는 데 사용되는 주요 기법 중 하나가 바로 빅오(Big O) 분석입니다.

빅오 분석을 통해 개발자는 가장 효과적이고 확장 가능한 알고리즘을 선택할 수 있습니다. 이 글에서는 빅오 표기법에 대한 핵심 내용을 다루는 상세한 안내를 제공합니다.

빅오 분석이란 무엇인가?

빅오 분석은 알고리즘이 입력 크기 증가에 따라 어떻게 동작하는지를 평가하는 방법입니다. 특히, 입력 데이터의 크기가 커질 때 알고리즘의 효율성이 어떻게 변화하는지를 중점적으로 분석합니다.

효율성이란 알고리즘이 결과를 생성하는 과정에서 시스템 자원을 얼마나 효과적으로 사용하는지를 나타냅니다. 여기서 가장 중요한 자원은 시간과 메모리입니다.

따라서 빅오 분석에서 고려하는 주요 질문은 다음과 같습니다.

• 입력 크기가 커짐에 따라 알고리즘의 메모리 사용량은 어떻게 변하는가?
• 입력 크기가 커짐에 따라 알고리즘이 결과를 생성하는 데 걸리는 시간은 어떻게 변하는가?

첫 번째 질문에 대한 답은 알고리즘의 공간 복잡도이고, 두 번째 질문에 대한 답은 시간 복잡도입니다. 이러한 복잡성을 표현하기 위해 빅오 표기법이라는 특별한 방식을 사용합니다. 빅오 표기법에 대한 자세한 내용은 이 글의 뒷부분에서 다루겠습니다.

사전 지식

이 글을 최대한 활용하기 위해서는 기본적인 대수학 지식이 필요합니다. 또한, 예시 코드에서 파이썬을 사용하므로 파이썬에 대한 기본적인 이해가 있으면 도움이 됩니다. 코드를 직접 작성할 필요는 없으므로 깊이 있는 지식은 요구되지 않습니다.

빅오 분석 수행 방법

이 섹션에서는 빅오 분석을 실제로 수행하는 방법에 대해 설명합니다.

빅오 복잡도 분석을 할 때 알고리즘의 성능은 입력 데이터의 구조에 따라 달라질 수 있다는 점을 기억해야 합니다.

예를 들어, 정렬 알고리즘은 이미 정렬된 데이터에서는 매우 빠르게 작동하지만, 역순으로 정렬된 데이터에서는 가장 느리게 작동합니다. 이것이 각각 최선 및 최악의 시나리오입니다.

빅오 분석에서는 주로 최악의 시나리오를 기준으로 알고리즘을 평가합니다.

공간 복잡도 분석

공간 복잡도 분석은 입력 크기가 증가함에 따라 알고리즘이 사용하는 추가 메모리의 양이 어떻게 변하는지를 측정합니다.

예를 들어, 다음 코드는 재귀 호출을 사용하여 n부터 0까지 반복합니다. 이 알고리즘의 공간 복잡도는 입력 크기 n에 비례합니다. 왜냐하면 n이 증가할수록 함수 호출 스택에 쌓이는 함수의 호출 횟수도 증가하기 때문입니다. 따라서 이 알고리즘의 공간 복잡도는 O(n)입니다.

def loop_recursively(n):
    if n == -1:
        return
    else:
        print(n)
        loop_recursively(n - 1)

다음은 더 효율적인 구현 방식입니다.

def loop_normally(n):
    count = n
    while count >= 0:
        print(count)
        count =- 1

위의 알고리즘에서는 추가 변수 하나만 사용하고 이를 이용해 반복합니다. n이 아무리 커져도 추가적으로 필요한 변수는 하나뿐입니다. 따라서 이 알고리즘의 공간 복잡도는 'O(1)'로 표현되는 상수 복잡도입니다.

위의 두 알고리즘의 공간 복잡도를 비교해 보면 while 루프를 사용하는 것이 재귀 호출보다 효율적임을 알 수 있습니다. 이것이 빅오 분석의 주된 목표입니다. 즉, 입력 크기가 증가함에 따라 알고리즘의 효율성이 어떻게 변화하는지를 분석하는 것입니다.

시간 복잡도 분석

시간 복잡도 분석에서는 알고리즘이 실행되는 총 시간에 초점을 맞추기보다, 입력 크기가 증가함에 따라 필요한 계산 단계 수가 어떻게 변화하는지를 분석합니다. 실제 실행 시간은 다양한 시스템 및 환경적 요인에 의해 영향을 받기 때문입니다. 따라서 우리는 계산 단계의 증가만을 추적하고 각 단계가 동일한 시간을 소비한다고 가정합니다.

시간 복잡도 분석을 설명하기 위해 다음 예시를 살펴보겠습니다.

각 사용자가 고유 ID와 이름을 가지고 있는 사용자 목록이 있다고 가정합니다. 우리의 목표는 특정 ID가 주어졌을 때 해당 ID를 가진 사용자의 이름을 반환하는 함수를 구현하는 것입니다. 다음은 가능한 구현 방법입니다.

users = [
    {'id': 0, 'name': 'Alice'},
    {'id': 1, 'name': 'Bob'},
    {'id': 2, 'name': 'Charlie'},
]

def get_username(id, users):
    for user in users:
        if user['id'] == id:
            return user['name']
    return 'User not found'

get_username(1, users)

위의 알고리즘은 주어진 사용자 목록에서 올바른 ID를 가진 사용자를 찾기 위해 전체 목록을 순회합니다. 사용자가 3명이라면 알고리즘은 3번 반복하고, 10명이면 10번 반복합니다.

따라서 알고리즘의 단계 수는 사용자 수에 정비례하여 증가합니다. 이러한 알고리즘을 선형 시간 복잡도를 가진다고 합니다. 하지만 알고리즘을 개선할 수 있습니다.

사용자를 목록 대신 딕셔너리에 저장한다고 가정해 봅시다. 그러면 사용자를 검색하는 알고리즘은 다음과 같습니다.

users = {
    '0': 'Alice',
    '1': 'Bob',
    '2': 'Charlie'
}

def get_username(id, users):
     if id in users:
         return users[id]
     else:
         return 'User not found'

get_username(1, users)

새로운 알고리즘에서 사용자가 3명일 때, 사용자 이름을 얻기 위해 특정 단계를 수행합니다. 10명일 때도 마찬가지입니다. 즉, 사용자 수가 증가하더라도 사용자 이름을 얻기 위한 단계 수는 변하지 않습니다.

이 알고리즘은 상수 시간 복잡도를 가집니다. 사용자 수가 아무리 많아도 계산 단계 수는 동일합니다.

빅오 표기법이란 무엇인가?

앞서 다양한 알고리즘의 빅오 공간 및 시간 복잡도를 계산하는 방법을 살펴보았습니다. 복잡도를 표현하기 위해 선형, 상수와 같은 용어를 사용했습니다. 빅오 표기법은 알고리즘의 복잡도를 나타내는 또 다른 방법입니다.

빅오 표기법은 알고리즘의 공간 또는 시간 복잡도를 표현하는 방법으로, 'O(함수)' 형태로 표현됩니다. 여기서 함수는 알고리즘의 복잡도를 나타냅니다.

선형 복잡도는 n으로 표현되므로 O(n)으로 쓰고, 상수 복잡도는 1로 표현되므로 O(1)로 씁니다.

더 복잡한 경우도 있지만, 일반적으로 알고리즘의 복잡도를 빅오 표기법으로 나타내는 단계는 다음과 같습니다.

• 입력 크기 n에 대한 수학 함수 f(n)를 정의합니다. 여기서 f(n)는 알고리즘이 사용하는 공간 또는 실행하는 계산 단계 수를 나타냅니다.
• 해당 함수에서 가장 지배적인 항을 선택합니다. 지배적인 항은 계승, 지수, 다항식, 2차, 선형, 로그, 상수 순으로 정렬됩니다.
• 선택된 항에서 계수를 제거합니다.

이렇게 얻은 항이 빅오 표기법의 괄호 안에 사용됩니다.

예시:

다음 파이썬 함수를 살펴봅시다.

users = [
    'Alice',
    'Bob',
    'Charlie'
]

def print_users(users):
    number_of_users = len(users)
    print("Total number of users:", number_of_users)

    for i in number_of_users:
        print(i, end=': ')
        print(user)

이제 이 알고리즘의 빅오 시간 복잡도를 계산해 보겠습니다.

먼저 알고리즘이 수행하는 계산 단계 수를 나타내는 수학 함수 f(n)를 정의해야 합니다. 여기서 n은 입력 크기를 나타냅니다.

위의 코드에서 함수는 사용자 수를 계산하고 출력하는 두 단계를 수행합니다. 그런 다음 각 사용자에 대해 인덱스를 출력하는 단계와 사용자 이름을 출력하는 단계를 수행합니다.

따라서 수행되는 계산 단계 수를 가장 잘 나타내는 함수는 f(n) = 2 + 2n으로 쓸 수 있습니다. 여기서 n은 사용자 수를 나타냅니다.

두 번째 단계로 가장 지배적인 항을 선택합니다. 여기서 2n은 선형 항이고, 2는 상수 항입니다. 선형 항이 상수 항보다 더 지배적이므로 2n을 선택합니다.

따라서 우리 함수는 이제 f(n) = 2n이 됩니다.

마지막 단계는 계수를 제거하는 것입니다. 우리 함수에서는 계수가 2이므로 이를 제거하면 f(n) = n이 됩니다. 이 항이 빅오 표기법의 괄호 안에 들어갈 항입니다.

따라서 우리 알고리즘의 시간 복잡도는 O(n), 즉 선형 복잡도입니다.

다양한 빅오 복잡도

이제 다양한 빅오 복잡도와 그에 따른 그래프를 살펴보겠습니다.

#1. 상수 복잡도

상수 복잡도는 알고리즘이 입력 크기에 상관없이 항상 일정한 양의 공간을 사용하거나 일정한 수의 단계를 수행한다는 것을 의미합니다. 이것은 가장 효율적인 복잡도이며, 알고리즘의 확장성이 매우 높다는 것을 의미합니다.

상수 복잡도는 O(1)로 표현됩니다. 하지만 항상 상수 시간 복잡도를 가지는 알고리즘을 작성할 수 있는 것은 아닙니다.

#2. 로그 복잡도

로그 복잡도는 O(log n)으로 표현됩니다. 컴퓨터 과학에서 로그의 밑이 지정되지 않으면 보통 2로 간주합니다.

따라서 log n은 log2n을 의미합니다. 로그 함수는 초기에 빠르게 증가하지만, 입력 크기가 커질수록 증가 속도가 느려집니다. 이는 알고리즘이 큰 입력 크기에서도 효율적으로 작동한다는 것을 의미합니다.

#3. 선형 복잡도

선형 함수에서는 독립변수가 p배 증가하면 종속변수도 p배 증가합니다.

따라서 선형 복잡도를 갖는 함수는 입력 크기와 동일한 비율로 단계 수가 증가합니다. 입력 크기가 두 배가 되면 계산 단계나 메모리 사용량도 두 배가 됩니다. 선형 복잡도는 O(n)으로 표시됩니다.

#4. 선형 로그 복잡도

선형 로그 복잡도는 O(n * log n)으로 표현됩니다. 이것은 선형 함수와 로그 함수의 곱으로 나타낼 수 있습니다. 따라서 n이 커질수록 로그 함수가 1보다 큰 값을 가지므로 선형 복잡도보다 조금 더 큰 결과를 보입니다.

로그 n은 n이 2보다 큰 모든 값에 대해 1보다 큽니다. 따라서 선형 로그 함수는 대부분의 경우 선형 함수보다 확장성이 떨어집니다.

#5. 2차 복잡도

2차 복잡도는 O(n²)으로 표현됩니다. 입력 크기가 10배 증가하면 계산 단계나 메모리 사용량이 10²배, 즉 100배 증가합니다. 이는 확장성이 매우 낮으며, 그래프에서 볼 수 있듯이 복잡도가 매우 빠르게 증가합니다.

예를 들어 버블 정렬과 같이 n번 반복하고 각 반복에서 다시 n번 반복하는 알고리즘에서 2차 복잡도가 발생합니다. 일반적으로 이상적이지 않지만, 때로는 2차 복잡도를 가진 알고리즘을 선택할 수밖에 없는 경우도 있습니다.

#6. 다항 복잡도

다항 복잡도를 갖는 알고리즘은 O(np)로 표현됩니다. 여기서 p는 상수 정수이며, n이 증가하는 차수를 나타냅니다. 이러한 복잡도는 중첩 루프가 많이 사용될 때 발생합니다. 2차 복잡도와 다항 복잡도의 차이는 2차는 p가 2인 경우이고, 다항식은 p가 2보다 큰 값을 갖는다는 것입니다.

#7. 지수 복잡도

지수 복잡도는 다항 복잡도보다 훨씬 빠르게 증가합니다. 수학에서 지수 함수의 기본값은 상수 e(오일러 수)이지만, 컴퓨터 과학에서는 2를 기본값으로 사용합니다.

지수 복잡도는 O(2n)으로 표시됩니다. n이 0이면 2n은 1이 되지만, n이 5로 증가하면 2n은 32가 됩니다. 즉, n이 1 증가할 때마다 이전 값이 두 배가 됩니다. 따라서 지수 함수는 확장성이 매우 낮습니다.

#8. 계승 복잡도

계승 복잡도는 O(n!)으로 표시됩니다. 이 함수는 또한 매우 빠르게 증가하므로 확장이 거의 불가능합니다.

결론

이 글에서는 빅오 분석의 기본 개념과 다양한 복잡도에 대해 알아보았습니다. 또한 각 복잡도가 알고리즘의 확장성에 미치는 영향에 대해서도 논의했습니다.

다음으로는 파이썬으로 구현된 정렬 알고리즘에 대한 빅오 분석을 연습해 보는 것이 좋습니다.