Time Complexity(시간복잡도)

✅ Time Complexity(시간복잡도)

알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 크기에 따라 분석한 것입니다. 간단히 말해서, 주어진 알고리즘이 처리해야 할 데이터의 양이 커질수록, 그 알고리즘이 얼마나 더 오래 걸리는지를 나타내는 척도입니다. 시간 복잡도를 잘 이해하면, 프로그램을 더 효율적으로 만들 수 있습니다.

 

시간복잡도 분석

알고리즘의 성능을 분석할 때, 주로 입력 크기(n)에 대한 함수로 표현합니다. 예를 들어, 입력 크기가 두 배가 되면 알고리즘의 실행 시간이 어떻게 변하는지 알 수 있습니다. 가장 일반적인 시간 복잡도는 빅오 표기법(Big-O Notation)을 사용하여 나타냅니다.

 

✅ 빅오 표기법 표

시간 복잡도	설명 예시	알고리즘
O(1)	상수 시간 – 입력 크기와 관계없이 실행 시간이 일정	배열의 특정 요소 접근, 해시 테이블 조회
O(log n)	로그 시간 – 입력 크기가 커질수록 시간이 천천히 증가	이진 탐색, 이진 힙 연산
O(n)	선형 시간 – 입력 크기와 비례해서 실행 시간이 증가	배열 순회, 리스트에서 값 찾기
O(n log n)	선형 로그 시간 – n과 log n의 곱이 시간 복잡도	병합 정렬, 퀵 정렬, 힙 정렬
O(n^2)	이차 시간 – 입력 크기의 제곱만큼 실행 시간이 증가	버블 정렬, 선택 정렬, 삽입 정렬
O(2^n)	지수 시간 – 입력 크기가 커지면 시간이 급격히 증가	피보나치 재귀, 부분 집합 구하기
O(n!)	팩토리얼 시간 – 매우 비효율적인 알고리즘	여행하는 외판원 문제(순열 탐색)

 

빅오 표기법 이해

O(1): 일정 시간 내에 작업을 끝낼 수 있습니다. 예를 들어 배열에서 특정 인덱스에 접근하는 것은 항상 일정 시간이 걸립니다.

O(log n): 예를 들어 이진 탐색처럼 데이터를 반씩 나누면서 탐색하는 알고리즘에서는 데이터가 커질수록 실행 시간이 느리지만, 그 속도가 매우 천천히 증가합니다.

O(n): 배열을 순차적으로 탐색하거나, 리스트에서 특정 값을 찾는 등의 알고리즘에서 나타나는 시간 복잡도입니다.

O(n log n): 분할 정복 기법을 사용하는 알고리즘(병합 정렬, 퀵 정렬 등)은 대개 이 시간 복잡도를 가집니다. 데이터 크기가 두 배가 되면 처리 시간이 약간 더 두 배가 아니라 약간 더 많은 시간이 걸립니다.

O(n^2): 중첩된 루프가 있을 때 발생합니다. 예를 들어, 배열의 모든 요소에 대해 다시 다른 요소를 비교하는 버블 정렬이나 삽입 정렬에서는 n이 커질수록 시간이 제곱으로 증가합니다.

O(2^n): 지수 시간 복잡도는 매우 비효율적입니다. 입력 크기(n)가 하나씩 증가할 때마다 실행 시간이 두 배씩 증가합니다. 이 정도 시간 복잡도를 가진 알고리즘은 매우 큰 문제를 풀기에는 비효율적입니다.

O(n!): 팩토리얼 시간 복잡도는 문제의 가능한 모든 순서를 탐색해야 할 때 나타납니다. 예를 들어, 여행하는 외판원 문제처럼 모든 가능한 경로를 계산해야 하는 경우입니다.

 

---

 

# O(1) : 상수 시간
def constant_time_example(arr):
    return arr[0]  # 첫 번째 요소에 접근하는 것은 일정한 시간이 걸림

# O(log n) : 로그 시간
def binary_search_example(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 찾지 못한 경우

# O(n) : 선형 시간
def linear_time_example(arr):
    for element in arr:
        print(element)  # 모든 요소를 출력하는 데 선형 시간이 걸림

# O(n^2) : 이차 시간
def quadratic_time_example(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])  # 두 개의 중첩된 루프

# O(n log n) : 선형 로그 시간
def merge_sort_example(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_example(arr[:mid])
    right = merge_sort_example(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left)
    result.extend(right)
    return result


# O(2^n) : 지수 시간
def exponential_time_example(n):
    if n == 0:
        return 1
    return exponential_time_example(n - 1) + exponential_time_example(n - 1)  # 재귀로 2^n 계산

# O(n!) : 팩토리얼 시간
from itertools import permutations

def factorial_time_example(arr):
    return list(permutations(arr))  # 배열의 모든 순열을 구하는 데 팩토리얼 시간이 걸림