시간복잡도 - 개념

시간복잡도를 계산하는 방법

1. 알고리즘의 기본 단계 분석: 알고리즘이 수행하는 기본 작업(예: 비교, 덧셈, 루프 등)의 수를 세어야 함
2. 입력 크기에 대한 함수 작성: 입력 크기에 따라 기본 작업의 수가 어떻게 변하는지 나타내는 수식을 만듭니다. 입력 크기는 보통 n으로 표기됨
3. 주요 작업의 기여도 평가: 여러 단계가 있는 알고리즘에서는 각 단계의 기여도를 평가합니다. 가장 큰 기여도를 가진 단계가 전체 시간복잡도를 결정함
4. 최대값을 추출하고 단순화: 시간이 가장 많이 소요되는 부분을 기준으로 시간복잡도를 단순화하여 표기합니다. 이때 O(n), O(n^2), O(log n) 등의 표기법을 사용함

시간복잡도는 O(n)

왜냐하면 n개의 요소를 반복

def example1(arr):
    for i in range(len(arr)):  # n번 반복
        print(arr[i])

시간복잡도는 O(n^2)

 

두 개의 중첩 루프가 각각 n번 반복되므로 전체 작업 수는 n * n

def example2(arr):
    for i in range(len(arr)):  # n번 반복
        for j in range(len(arr)):  # n번 반복
            print(arr[i], arr[j])

시간복잡도는 O(log n)

이진 검색 알고리즘은 배열의 크기가 반으로 줄어들면서 검색을 계속함

def example3(arr, target):
    low, high = 0, 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