알고리즘: 시간복잡도

Time Complexity

time complexity

Author

Cheonghyo Cho

시간 복잡도란

시간 복잡도는 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 변화하는지를 나타내는 척도이다. 일반적으로 Big O 표기법을 사용하여 표현되며, 예를 들어 \(O(n), O(\log n), O(n^2)\) 등으로 표현된다.

시간 복잡도의 종류

이름	시간복잡도	설명	Example algorithms
constant time	\(O(1)\)	입력의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘	정렬된 수 배열에서 중간값 찾기
logarithmic time	\(O(\log n)\)	알고리즘의 실행 시간이 입력 크기의 로그에 비례해서 증가, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬	이진검색(Binary search)
linear time	\(O(n)\)	알고리즘의 실행 시간이 입력 크기에 직접 비례(1:1)해서 증가	배열을 순회하는 알고리즘(반복문)
linearithmic time	\(O(n \log n)\)	알고리즘의 실행 시간이 입력 크기에 비례하여 증가하지만, 각 단계마다 로그 시간이 추가로 소요	quick-sort나 병합 정렬과 같은 효율적인 정렬 알고리즘
quadratic time	\(O(n^2)\)	알고리즘의 실행 시간이 입력 크기의 제곱에 비례해서 증가	버블 정렬, 삽입 정렬과 같은 간단한 정렬 알고리즘, 반복문이 두번
factorial time	\(O(n!)\)	알고리즘의 실행 시간이 입력 크기의 팩토리얼만큼 증가
exponential time	\(O(2^n)\)	알고리즘의 실행 시간이 입력 크기의 지수적으로 증가	brute-force search를 통한 matrix chain multiplication

시간 복잡도 예시

#1

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 타겟을 찾으면 해당 인덱스 반환
    return -1  # 타겟을 찾지 못하면 -1 반환

linear_search([0,2,3,4], 5)

-1

최악의 경우(Worst Case) 시간 복잡도: 타겟 값이 배열의 마지막에 위치하거나 배열 내에 존재하지 않는 경우, 배열의 모든 요소를 검사해야 하며, 입력 크기 n에 대해 n번의 비교가 이루어짐: \(O(n)\)
최선의 경우(Best Case) 시간 복잡도: 타겟 값이 배열의 첫 번째 위치에 있으면, 첫 번째 비교에서 바로 타겟을 찾을 수 있음: \(O(1)\)
평균적인 경우(Average Case) 시간 복잡도: 타겟 값의 위치가 무작위일 때, 타겟을 찾기까지 배열의 절반 정도를 평균적으로 검사해야 함. 그러나 평균적인 경우도 최악의 경우와 마찬가지로 n에 비례하기 때문에, 평균 시간 복잡도 역시 \(O(n)\)

# 2

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid  # 타겟을 찾은 경우
        if guess > target:
            high = mid - 1  # 타겟이 중간값보다 작은 경우, 검색 범위를 낮은 쪽으로 조정
        else:
            low = mid + 1  # 타겟이 중간값보다 큰 경우, 검색 범위를 높은 쪽으로 조정
    return -1  # 타겟을 찾지 못한 경우

예를 들어, \(n=16\)인 정렬된 배열에서 특정 값을 이진 검색으로 찾는 경우를 생각해봅시다. 최악의 경우나 평균적인 경우에도 검색 횟수는 다음과 같이 계산됨.

처음 검색 범위는 전체 배열. (n=16)
첫 번째 비교 후, 검색 범위는 8개의 요소로 감소. (n/2)
두 번째 비교 후, 검색 범위는 4개의 요소로 감소. (n/4)
세 번째 비교 후, 검색 범위는 2개의 요소로 감소. (n/8)
네 번째 비교 후, 검색 범위는 1개의 요소로 감소. (n/16)

이 경우, 최대 4번의 비교로 타겟 값을 찾을 수 있으며, 이는 \(\log_2 16=4\)와 일치함. 따라서, 이진 검색의 시간 복잡도는 \(O(\log n)\).

참고자료

위키피디아(https://wikipedia.org)