빅오 표기법에 따른 파이썬 코드 예시

시간 복잡도를 표현하는 빅오 표기법을 실제 파이썬 코드 예시와 함께 살펴보도록 하겠다. 시간 복잡도는 알고리즘의 성능과 효율성을 나타내는 지표로 사용된다. 코딩 테스트에서는 주어진 문제의 제약과 시간 복잡도에 맞는 알고리즘을 선택하여 효율적인 코드를 작성하는 것이 중요하다. 따라서 빅오 표기법을 고려하면 다양한 알고리즘의 성능을 분석하고 개선해 볼 수 있다.

 

반응형

 

시간 복잡도	예시	설명
O(1)	리스트 인덱싱	인덱스를 통해 리스트의 요소에 접근하는 작업은 일정한 시간이 소요됨
O(logn)	이진 탐색	정렬된 리스트에서 특정 값을 찾는 작업은 탐색 범위를 반으로 나누며, 탐색 속도가 로그에 비례
O(n)	선형 탐색	리스트의 모든 요소를 한 번씩 확인하는 작업은 입력 크기에 비례하여 진행됨
O(nlogn)	병합 정렬	리스트를 반으로 분할하고 재귀적으로 정렬하며, 분할된 부분 리스트를 병합하는 작업이 로그와 선형의 곱에 비례
O(n²)	이중 반복문	이중 반복문을 사용하여 리스트의 모든 요소 쌍을 확인하는 작업은 입력 크기의 제곱에 비례
O(2ⁿ)	부분 집합 생성	모든 부분 집합을 생성하기 위해 가능한 모든 조합을 확인하는 작업은 2의 입력 크기에 대한 지수적인 시간이 소요됨
O(n!) - n 팩토리얼 시간	순열 생성	모든 가능한 순열을 생성하는 작업은 입력 크기에 대해 매우 큰 시간이 소요됨

 

1. O(1): 상수 시간

O(1) 시간 복잡도는 입력 크기에 관계없이 항상 일정한 실행 시간을 가지는 알고리즘을 의미한다. 즉, 입력의 크기에 관계없이 일정한 시간만큼의 연산을 수행한다. O(1) 알고리즘은 매우 효율적이며 실행 시간이 상수로 고정되어 있기 때문에 가장 이상적인 시간 복잡도이다.

파이썬에서 O(1) 시간 복잡도 예:

1) 리스트, 튜플, 문자열 등의 인덱스로 요소에 접근하는 경우

def get_first_element(lst):
    return lst[0]

위의 코드는 주어진 리스트에서 첫 번째 요소를 반환하는 함수다. 이 함수는 리스트의 크기에 관계없이 항상 첫 번째 요소를 반환하는데, 이 연산은 상수 시간에 이루어진다. 즉, 입력 리스트의 크기가 어떻든지 상관없이 항상 동일한 실행 시간을 가진다. 따라서 이 함수의 시간 복잡도는 O(1)이다. 파이썬의 시퀀스 자료형에서는 인덱스를 사용하여 특정 위치에 있는 요소에 접근하는 연산이 O(1) 시간에 수행된다.

2) 사전(Dictionary)에서 키(Key)를 사용하여 값(Value)에 접근하는 경우

파이썬의 사전은 해시 테이블을 기반으로 구현되어 있어서 특정 키를 사용하여 값을 찾는 연산이 평균적으로 O(1) 시간에 수행된다.

3) 산술 연산과 비트 연산

파이썬의 산술 연산자와 비트 연산자는 입력의 크기와 상관없이 항상 일정한 시간에 수행되므로 O(1) 시간 복잡도를 가진다.

4) 객체의 메서드 호출

객체의 메서드 호출은 해당 메서드의 구현에 따라 다르지만, 대부분의 경우 메서드 호출은 상수 시간에 수행된다.

5) 슬라이싱(Slicing)

파이썬의 슬라이싱 연산은 원본 객체를 복사하지 않고 새로운 슬라이스 객체를 생성하기 때문에 O(1) 시간에 수행된다.

6) 크기가 고정된 작업

입력 크기와 상관없이 항상 일정한 크기의 작업을 수행하는 경우, 해당 작업은 O(1) 시간에 수행된다.

 

2. O(logn): 로그 시간

O(logn) 시간 복잡도를 갖는 대표적인 예시로 이진 탐색(Binary Search) 알고리즘이 있다. 이진 탐색은 정렬된 리스트에서 특정 값을 찾는 알고리즘으로, 반씩 범위를 줄여가며 탐색을 수행한다.

이진 탐색은 매 반복마다 탐색 범위를 절반으로 줄이므로, 입력 크기 n에 대해 O(logn)의 시간 복잡도를 가진다. 이 알고리즘은 정렬된 리스트에서 특정 값을 효율적으로 찾을 때 사용된다.

예: 이진 탐색, 이진트리, 이진 힙, 분할 정복, 이진 검색 트리

위와 같은 알고리즘은 입력의 크기에 따라 탐색 범위를 반으로 나누거나, 이진트리 구조를 활용하여 탐색을 효율적으로 수행한다. 이를 통해 O(logn)의 시간 복잡도를 달성할 수 있다.

 

정렬된 리스트 arr에서 target 값을 이진 탐색하여 해당 값의 인덱스를 반환하는 함수 예시

def binary_search(arr, target):
    low = 0 # 첫번째 인덱스로 초기화
    high = len(arr) - 1 # 마지막 인덱스로 초기화

    # 반복문을 통해 low와 high가 교차할 때까지 실행
    while low <= high:
        mid = (low + high) // 2
        # target 값과 mid 값이 같으면 mid가 target이므로 mid 반환
        if arr[mid] == target:
            return mid
        # target이 mid보다 크면 low를 mid+1로 업데이트하여 범위를 오른쪽으로 줄인다.
        elif arr[mid] < target:
            low = mid + 1
        # target이 mid보다 작으면 high를 mid-1로 업데이트하여 범위를 왼쪽으로 줄인다.
        else:
            high = mid - 1
    # target이 없는 경우 -1 반환
    return -1

 

3. O(n): 선형 시간

입력 크기에 비례하여 선형적으로 연산이 증가한다. 입력 크기가 두 배로 늘어나면 연산도 두 배로 증가한다. 예를 들어, 리스트의 모든 요소를 한 번씩 확인하는 경우를 말한다.

예: 리스트의 모든 요소를 출력하는 경우

리스트의 크기에 비례하여 모든 요소를 한 번씩 출력하기 때문에 시간 복잡도는 O(n)이다.

def print_list(lst):
    for item in lst:
        print(item)

 

4. O(nlogn): 선형 로그 시간

입력 크기에 비례하여 연산이 증가하지만, 로그 함수의 형태로 증가한다. 입력 크기가 두 배로 늘어나면 연산은 약간 더 많아지지만 비례적으로 늘어나지 않는다. 정렬 알고리즘인 병합 정렬과 퀵 정렬이 이에 해당한다.

예: 정렬 알고리즘 (병합 정렬, 퀵 정렬 등)

병합 정렬은 리스트를 반으로 나누고, 나누어진 부분 리스트를 정렬한 후 병합하는 과정을 재귀적으로 수행한다. 이때, 리스트를 나누는 과정은 O(logn)이며, 각 부분 리스트를 병합하는 과정은 O(n)이다. 따라서 전체 시간 복잡도는 O(nlogn)이다.

 

병합 정렬 알고리즘을 재귀적으로 구현한 예시 코드

# 정렬된 리스트 반환
def merge_sort(lst):
    # 리스트의 길이가 1 이하인 경우 그대로 반환
    if len(lst) <= 1:
        return lst
    # 리스트를 반으로 나누어 재귀적으로 호출
    mid = len(lst) // 2
    left = merge_sort(lst[:mid]) # 첫 번째부터 중간까지의 요소
    right = merge_sort(lst[mid:]) # 중간부터 마지막까지의 요소
    return merge(left, right) # 병합

# 두 개의 정렬된 리스트 병합
def merge(left, right):
    result = []
    while left and right: # 리스트가 모두 비어있지 않은 동안 반복문을 실행
        # left와 right의 첫 번째 요소를 비교하고, 작은 값을 result에 추가
        if left[0] < right[0]:
            # 추가한 요소는 원본 리스트에서 제거
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 남아있는 리스트의 모든 요소를 result에 추가
    if left:
        result.extend(left)
    if right:
        result.extend(right)
    # 정렬이 완료된 result 리스트 반환
    return result

 

※ 파이썬의 sort()는 O(nlogn)이다.

파이썬의 sort() 함수가 O(nlogn)인 이유는 주로 퀵 정렬(Quick Sort) 알고리즘을 기반으로 구현되어 있기 때문이다. 퀵 정렬은 분할 정복(Divide and Conquer) 방법을 사용하여 리스트를 정렬한다. 이 알고리즘은 다음과 같은 과정으로 진행된다.

1. 리스트에서 하나의 원소를 기준으로 선택한다. 이를 피벗(Pivot)이라고 한다.
2. 피벗을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할한다.
3. 분할된 두 개의 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행한다.
4. 재귀 호출을 통해 정렬된 부분 리스트들을 병합한다.

이 과정에서 평균적으로 각 분할 단계에서 피벗을 중심으로 리스트를 대략 반으로 나눌 수 있다. 이 때문에 퀵 정렬은 평균적으로 O(nlogn)의 시간 복잡도를 가지게 된다.

하지만 최악의 경우, 퀵 정렬은 이미 정렬된 리스트에서 가장 작거나 가장 큰 요소를 피벗으로 선택하는 경우에는 분할이 제대로 이루어지지 않아 시간 복잡도가 O(n^2)까지 증가할 수 있다. 이러한 최악의 경우를 피하기 위해 피벗을 랜덤 하게 선택하거나, 최적화된 피벗 선택 방법을 사용하는 것이 일반적이다.

파이썬의 sort() 함수는 퀵 정렬을 기반으로 하되, 최적화된 알고리즘과 피벗 선택 방법을 사용하여 평균적으로 O(nlogn)의 성능을 제공한다. 그렇기 때문에 대부분의 경우 sort() 함수는 효율적인 정렬을 수행할 수 있다.

 

5. O(n²): 이차 시간

입력 크기의 제곱에 비례하여 연산이 증가한다. 입력 크기가 두 배로 늘어나면 연산은 네 배로 증가한다. 예를 들어, 이중 반복문을 사용하여 리스트의 모든 쌍을 확인하는 경우가 있다.

예: 이중 반복문을 사용하는 경우

이중 반복문을 사용하여 리스트의 모든 쌍을 출력하는 경우, 외부 반복문은 n번 실행되고 내부 반복문은 n-1, n-2, …, 2, 1번 실행됩니다. 따라서 전체 시간 복잡도는 약 n*(n-1)/2로 표현할 수 있으며, 이는 O(n^2)입니다.

 

이중 반복문 예시 코드

def print_pairs(lst):
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            print(lst[i], lst[j])

 

6. O(2ⁿ): 지수 시간

시간 복잡도가 O(2ⁿ)인 경우는 주로 부분집합(Subsets) 생성이나 조합적 문제에서 발생한다. 이러한 문제는 주어진 집합의 모든 부분집합 또는 가능한 조합을 생성해야 하기 때문에, 경우의 수가 2ⁿ 개인 지수적으로 증가한다.

 

집합의 모든 부분집합을 생성하는 예시 코드

def generate_subsets(nums):
    subsets = []
    n = len(nums)

    # 0부터 2^n까지의 모든 숫자에 대해 반복
    for i in range(2 ** n):
        subset = []

        # 해당 비트가 1인 원소를 subset에 추가
        for j in range(n):
            if (i >> j) & 1:
                subset.append(nums[j])

        subsets.append(subset)

    return subsets

위의 코드는 주어진 리스트 nums의 모든 부분집합을 생성하는 함수이다. 이중 반복문을 사용하여 0부터 2^n까지의 모든 숫자에 대해 비트 연산을 수행하고, 해당 비트가 1인 원소를 부분집합에 추가한다. 이를 통해 모든 가능한 부분집합을 생성하므로 시간 복잡도는 O(2ⁿ)이 된다.

주의할 점은 지수 시간 복잡도를 가지는 알고리즘은 입력 크기에 따라 매우 빠르게 증가하므로, 입력의 크기가 큰 경우에는 계산 시간이 급격히 증가할 수 있다. 따라서 가능하면 다른 접근 방법이나 최적화 기법을 고려해야 한다.

 

7. O(n!): n 팩토리얼 시간

n!은 n의 팩토리얼을 나타내며, n부터 1까지의 모든 자연수를 곱한 값을 의미한다. n이 증가할수록 시간이 기하급수적으로 증가한다.

n! = n * (n-1) * (n-2) * ... * 2 * 1

O(n!) 시간 복잡도는 입력 크기 n에 대해 가능한 모든 순열을 생성하고 처리하는 경우에 해당한다. 예를 들어, n개의 요소로 이루어진 모든 순열을 구하는 경우, 시간 복잡도는 O(n!)이 된다.

n!은 매우 빠르게 증가하는 함수이기 때문에 n이 작을 때는 상대적으로 빠른 실행 시간을 갖지만, n이 커질수록 실행 시간이 급격하게 증가한다. 따라서 n! 시간 복잡도는 매우 큰 입력에 대해 비효율적이며, 일반적으로 효율적인 알고리즘을 설계하기 위해 피해야 한다.

 

n 팩토리얼 시간 복잡도를 가지는 예시 코드

def permutation(arr):
    if len(arr) == 1:
        return [arr]

    result = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for p in permutation(rest):
            result.append([arr[i]] + p)

    return result

위의 코드는 리스트 arr의 모든 순열을 반환하는 함수이다. 함수 내부에서 재귀적으로 순열을 생성하고, 각각의 순열은 원소 하나를 선택하고 나머지 원소들에 대해 순열을 생성하는 방식으로 구현되어 있다. 이러한 방식으로 모든 가능한 순열을 생성하므로 시간 복잡도는 O(n!)이 된다.

n 팩토리얼 시간 복잡도를 가지는 알고리즘은 n이 큰 값일 경우에 매우 비효율적이다. 따라서 가능하면 다른 접근 방법이나 최적화 기법을 고려해야 한다.