알고리즘의 시간 복잡도: 주요 시간 복잡도와 예시

 

프로그래밍을 배우다 보면 알고리즘의 시간 복잡도라는 개념을 자주 접하게 됩니다.

시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 측정하는 방법으로, 알고리즘의 효율성을 평가하는 중요한 지표입니다. 이번 포스트에서는 시간 복잡도를 쉽게 이해할 수 있도록, 다양한 시간 복잡도의 예시를 소개하고 그 의미를 설명하겠습니다.

1. 시간 복잡도란?

시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타내는 측정 방법입니다.

입력 크기(n)가 커질수록 알고리즘이 소요하는 시간이 어떻게 변화하는지를 분석하는 데 사용됩니다. 가장 흔히 사용하는 표기법은 빅오 표기법(Big O Notation)입니다.

2. 주요 시간 복잡도와 예시

O(1) - 상수 시간 알고리즘

O(1) 알고리즘은 입력 크기와 관계없이 일정한 시간이 소요되는 알고리즘을 말합니다. 즉, 데이터의 양이 늘어나도 처리 시간은 변하지 않습니다.

예시

def print_first(my_list):
    print(my_list[0])

이 함수는 리스트의 첫 번째 요소를 출력하는데, 리스트의 크기와 상관없이 항상 한 번의 작업만 필요하므로 시간 복잡도는 O(1)입니다.

O(n) - 선형 시간 알고리즘

O(n) 알고리즘은 입력 크기와 실행 시간이 비례하는 경우를 말합니다. 입력 크기가 두 배로 늘어나면 실행 시간도 두 배로 증가합니다.(반복문)

예시 1

def print_each(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

이 함수는 리스트의 모든 요소를 순회하여 출력합니다. 리스트의 크기가 n이라면 n번 반복되므로 시간 복잡도는 O(n)입니다.

예시 2

def print_half(my_list):
    for i in range(len(my_list) // 2):
        print(my_list[i])

이 함수는 리스트의 앞 반쪽만을 출력합니다. 반복 횟수는 n/2이지만 상수 계수는 무시하므로 시간 복잡도는 O(n)입니다.

예시 3

def print_each_three_times(my_list):
    for i in range(len(my_list)):
        print(my_list[i])
    for i in range(len(my_list)):
        print(my_list[i])
    for i in range(len(my_list)):
        print(my_list[i])

이 함수는 리스트의 각 요소를 세 번 출력합니다. 각 반복문이 O(n)만큼 실행되지만, 계수를 무시하면 전체 시간 복잡도는 O(n)입니다.

O(n^2) - 이차 시간 알고리즘

O(n^2) 알고리즘은 반복문이 중첩되어 있을 때 발생하는 시간 복잡도입니다. 즉, 두 개의 중첩된 반복문이 있을 때 사용됩니다.

예시

def print_pairs(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            print(my_list[i], my_list[j])

이 함수는 리스트의 모든 쌍을 출력합니다. 두 개의 반복문이 각각 n번 반복되므로 시간 복잡도는 O(n^2)입니다.

O(log n) - 로그 시간 알고리즘

O(log n) 알고리즘은 입력 크기가 두 배로 증가할 때 반복 횟수가 일정 비율로 증가하는 알고리즘입니다. 일반적으로 이진 탐색에서 볼 수 있습니다.

예시

def binary_search(my_element, my_list):
    start_index = 0
    end_index = len(my_list) - 1
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if my_list[midpoint] == my_element:
            return midpoint
        elif my_element < my_list[midpoint]:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

이 함수는 정렬된 리스트에서 특정 요소를 찾기 위해 검색 범위를 반으로 줄여 나갑니다. 최대 반복 횟수는 로그 함수에 비례하므로 시간 복잡도는 O(log n)입니다.

O(n log n) - 선형 로그 시간 알고리즘

O(n log n) 알고리즘은 선형 시간 알고리즘이 로그 시간 알고리즘을 반복할 때 발생합니다. 주로 효율적인 정렬 알고리즘에서 볼 수 있습니다.

예시

def print_one_to_n(my_list):
    n = len(my_list)
    for i in range(1, n+1):
        print(binary_search(i, my_list))

def binary_search(my_element, my_list):
    start_index = 0
    end_index = len(my_list) - 1
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if my_list[midpoint] == my_element:
            return midpoint
        elif my_element < my_list[midpoint]:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

이 함수는 binary_search를 n번 호출합니다. 각 호출의 시간 복잡도는 O(log n)이므로 전체 시간 복잡도는 O(n log n)입니다.

3. 시간 복잡도 비교

시간 복잡도는 알고리즘의 효율성을 평가하는 중요한 지표입니다. 시간 복잡도가 낮을수록 입력 크기가 커져도 알고리즘이 더 빨리 실행됩니다. 일반적인 시간 복잡도는 다음과 같이 비교할 수 있습니다

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

시간 복잡도가 낮은 알고리즘을 사용하는 것이 성능이 좋으며, 문제를 해결하는 데 필요한 시간을 줄일 수 있습니다.

결론

시간 복잡도는 알고리즘의 성능을 평가하는 데 중요한 개념입니다.

다양한 시간 복잡도를 이해하고, 적절한 알고리즘을 선택하는 것이 효율적인 프로그래밍을 위한 핵심입니다.

이번 포스트를 통해 시간 복잡도의 기본 개념과 주요 예시를 쉽게 이해하시길 바랍니다!

공감과 댓글은 저에게 큰 힘이 됩니다.

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱