시간복잡도의 의미와 구하는 방법을 설명한다.

1. 시간복잡도란?

알고리즘의 효율성을 평가할 때 시간복잡도와 공간복잡도라는 두 가지 주요 개념이 있습니다. 둘 다 중요한 개념이지만 시간의 양을 사용하는 시간복잡도를 평가할 때 더 자주 사용합니다.

• 시간복잡도(Time Complexity): 알고리즘이 실행되는 데 걸리는 시간의 양을 입력 크기에 따라 나타낸 것입니다.
• 공간복잡도(Space Complexity): 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 입력 크기에 따라 나타낸 것입니다.

왜 시간복잡도가 중요한가?

알고리즘의 실행 시간을 측정할 때 단순히 코드의 시작과 끝 시간을 재는 방법도 있습니다. 아래와 같은 이유로 정확한 측정이 불가능 하게 됩니다.

• 컴퓨터 성능: 실행 시간은 사용하는 컴퓨터의 성능에 따라 크게 달라질 수 있습니다.
• 환경 요인: 실행 중인 다른 프로그램이나 시스템 상태 등 다양한 환경 요인에 영향을 받을 수 있습니다.

따라서 알고리즘의 성능을 공정하게 비교하기 위해서는 입력 크기에 따른 연산 횟수를 분석하는 시간복잡도를 사용하는 것이 더 적절합니다.

2. 시간복잡도 계산 연습

선형 탐색:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

주어진 배열에서 특정 값을 찾는 선형 탐색입니다. 최악의 경우, 배열의 모든 요소를 한 번씩 검사해야 하므로 시간복잡도는 O(n)입니다.

버블 정렬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 알고리즘입니다. 최악의 경우 모든 요소를 비교해야 하므로 시간복잡도는 O(n^2)입니다.

3. 최악

시간복잡도는 주로 Big-O 표기법을 사용하여 표현됩니다. Big-O 표기법은 입력 크기 n에 대해 알고리즘이 수행해야 할 연산의 상한선을 나타내며, 주로 최악의 경우를 기준으로 합니다. 일반적인 시간복잡도 표기는 다음과 같습니다:

• O(1): 상수 시간 - 입력 크기에 관계없이 일정한 시간이 걸림
• O(log n): 로그 시간 - 입력 크기가 커질수록 시간이 천천히 증가함
• O(n): 선형 시간 - 입력 크기에 비례하여 시간이 증가함
• O(n log n): 로그 선형 시간 - 입력 크기와 로그 크기의 곱에 비례하여 시간이 증가함
• O(n^2): 이차 시간 - 입력 크기의 제곱에 비례하여 시간이 증가함
• O(2^n): 지수 시간 - 입력 크기에 대한 지수 함수에 비례하여 시간이 증가함