시간 복잡도와 빅오 표기법

시간 복잡도

알고리즘이 입력 크기에 따라 실행되는 데 필요한 시간을 나타내는 것이다. 일반적으로 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타낸다. 보통 빅오 표기법을 사용하여 나타낸다. 이 표기법은 입력 크기에 대한 알고리즘 실행 시간의 상한을 나타내고, 주로 알고리즘의 실행 시간이 최악의 경우에 얼마나 증가하는지를 나타내는데 사용된다. 시간 복잡도를 고려하여 효율적인 알고리즘을 구현한다면 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화 한 코드를 구성했다는 의미이다. 

 

 

빅오 표기법(big-O notation)

입력값(n)에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도를 표현한다. 

최고차항을 기준으로 하는 이유는 연산의 수가 극한에 수렴할때 나머지 항이 복잡도에 미치는 영향은 미미하기 때문이다. 그래서 계수, 상수항은 무시하고 최고차항만으로 표현한다. 

대표적인 빅오 표기법에는 O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!)이 있다. 

아래는 각 표기법에 따라 소요되는 시간의 증가를 그래프로 나타낸 것이다. 

 

 

점근적 표기법(asymptotic notation)
알고리즘의 복잡도를 나타낼 때 계수, 상수항 등 중요하지 않은 항목을 무시하고 표현하는 것. 다음 3가지가 있다. 

- 최악의 경우 : 빅오 표기법(big-O notation)
- 평균의 경우 : 빅세타 표기법(big-θ notation)
- 최선의 경우 : 빅오메가 표기법(big-Ω notation)

 

 

O(1)

일정한 복잡도. 입력값이 증가해도 시간이 늘어나지 않는다. 

즉 입력값의 크기와 관계 없이 즉시 출력값을 얻어낼 수 있다. 

def get_first_element(arr):
    return arr[0]

my_list = [1, 2, 3, 4, 5]

first_element = get_first_element(my_list)
print(first_element)

# 리스트의 첫번째 요소를 출력함
# 실행 시간은 입력과 무관하게 항상 일정하다

 

O(n)

선형 복잡도. 입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다. 

def print_list_elements(arr):
    for element in arr:
        print(element)

my_list = [1, 2, 3, 4, 5]

# 리스트의 모든 요소를 출력. 리스트의 크기에 따라 횟수가 선형적으로 증가함
print_list_elements(my_list)

 

O(log n)

로그 복잡도. 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다. 주로 입력 크기에 따라 처리시간이 증가하는 정렬 알고리즘에서 많이 사용된다. 

# 이진 탐색
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

target_element = 7
index = binary_search(sorted_list, target_element)

if index != -1:
    print(f"{target_element}은(는) 인덱스 {index}에 있습니다.")
else:
    print(f"{target_element}을(를) 찾을 수 없습니다.")

 

O(n^2)

2차 복잡도. 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다. 쉬운 예시로는 반복문이 두번 있는 케이스가 있다. 

def print_combinations(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            print(matrix[i][j])

my_matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print_combinations(my_matrix)

 

O(C^n)

기하급수적 복잡도. 빅오 표기법중 가장 느린 시간 복잡도를 가진다. 재귀로 구현하는 피보나치 수열이 대표적인 알고리즘이다. 

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

n = 5
fibonacci_value = fibonacci(n)
print(f"{n}번째 값은 {fibonacci_value}입니다.")

 

 

 

 

시간 복잡도의 문제 해결 단계(빠른 순)

• O(1) - 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함
• O(log n) - 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
• O(n) - 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐
• O(n log n) : 문제를 해결하기 위한 단계의 수가 n * (log^2n)번 만큼의 수행 시간을 가짐. (선형 로그형)
• O(n^2) - 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
• O(C^n) - 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n제곱 

 

 

시간 복잡도를 구하는 요령

• 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우 : O(n)
• 컬렉션의 절반 이상을 반복하는 경우 : O(n/2) => O(n)
• 두개의 다른 루프를 사용하여 두 개의 개별 컬렉션을 반복할 경우 : O(n+m) => O(n)
• 두개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O(n^2)
• 두개의 중첩 루프를 사용하여 두 개의 다른 컬렉션을 반복 하는 경우 : O(n * m) => O(n^2)
• 컬렉션 정렬을 사용하는 경우 : O(n * log(n))

 

 

 

 

 

 

도움받은 글들

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/ 

https://blog.chulgil.me/algorithm/ 

https://joyhong-91.tistory.com/12