시간 복잡도, 빅오(Big O) 표기법 이란?

 

 

시간 복잡도는 입력이 커질수록 알고리즘이 실행되는 데 걸리는 시간을 나타냅니다. 작은 종이 더미보다 큰 종이 더미를 분류하는 데 시간이 더 오래 걸리는 것과 같습니다.
시간 복잡성에 대해 이야기할 때 알고리즘이 얼마나 빨리 성장하는지 설명하기 위해 "Big O" 표기법을 사용합니다.

예를 들어 시간 복잡도가 O(n)인 알고리즘은 입력 크기가 두 배가 되면 알고리즘을 실행하는 데 대략 두 배의 시간이 걸린다는 것을 의미합니다.
따라서 알고리즘의 시간 복잡도를 분석할 때 점점 더 큰 입력을 얼마나 빨리 처리할 수 있는지 묻고 있습니다. 알고리즘의 시간 복잡도가 낮으면 너무 많은 시간을 들이지 않고 큰 입력을 처리할 수 있음을 의미합니다.

시간 복잡도가 높으면 큰 입력을 효율적으로 처리하지 못할 수 있음을 의미합니다.
전반적으로 시간 복잡성은 다양한 작업에 대한 알고리즘을 비교하고 최적화하는 데 도움이 되기 때문에 컴퓨터 과학에서 중요한 개념입니다.

Big O의 "O"

Big O 표기법은 서로 다른 알고리즘의 효율성을 비교하고 주어진 작업에 가장 적합한 알고리즘을 선택하는 데 도움이 되기 때문에 컴퓨터 과학에서 중요합니다. 우리는 일반적으로 Big O 시간 복잡도가 낮은 알고리즘을 선호합니다. 입력 크기가 커짐에 따라 더 빠르게 실행되고 더 잘 확장되기 때문입니다.

 

O(1): 이는 일정한 시간 복잡도를 나타내며 알고리즘이 작업을 완료하는 데 걸리는 시간이 일정하고 입력 크기에 의존하지 않음을 의미합니다. 예를 들어 배열의 요소에 액세스 하는 것은 O(1) 시간 복잡도입니다.

 

목록의 요소에 액세스:

my_list = [1, 2, 3, 4, 5]
element = my_list[2] # Accessing the 3rd element

사전에서 값 찾기:

my_dict = {"apple": 3, "banana": 2, "orange": 1}
num_apples = my_dict["apple"] # Looking up the value associated with the key "apple"

문자열의 길이 확인:

my_string = "Hello, world!"
length = len(my_string) # Retrieving the length of the string

집합을 사용하여 구성원 확인:

my_set = {1, 2, 3, 4, 5}
is_member = 3 in my_set # Checking if the value 3 is in the set

이러한 예제는 입력 크기에 관계없이 실행하는 데 일정한 시간이 걸리기 때문에 모두 O(1) 시간 복잡도를 가집니다. 어떤 경우에는 일정한 시간 복잡도가 코드 자체에서 명확하지 않을 수 있지만(예를 들어 사전에서 값을 찾는 것은 내부적으로 여러 단계를 포함할 수 있음) 중요한 것은 알고리즘에 걸리는 시간입니다. 입력 크기에 의존하지 않습니다.

 

O(n): 이것은 선형 시간 복잡도를 나타내며, 이는 알고리즘이 작업을 완료하는 데 걸리는 시간이 입력 크기에 따라 선형적으로 증가함을 의미합니다. 예를 들어 배열이나 연결 목록을 통과하는 것은 O(n) 시간 복잡도입니다.

 

선형 검색:

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

이 함수는 대상 값을 찾기 위해 n개의 요소 목록을 통해 선형 검색을 수행합니다. 대상 값이 목록에 없는 최악의 경우 함수는 n개 요소를 모두 반복해야 하므로 O(n) 시간 복잡도가 발생합니다.

목록에서 최대값 찾기:

def find_max(my_list):
    max_val = my_list[0]
    for i in range(1, len(my_list)):
        if my_list[i] > max_val:
            max_val = my_list[i]
    return max_val

이 함수는 n개의 요소 목록을 반복하여 최대값을 찾습니다. 최대값이 목록의 끝에 있는 최악의 경우 함수는 n개의 모든 요소를 ​​반복해야 하므로 O(n) 시간 복잡도가 발생합니다.

 

목록 필터링:

def filter_list(my_list):
    new_list = []
    for i in range(len(my_list)):
        if my_list[i] % 2 == 0:
            new_list.append(my_list[i])
    return new_list

이 함수는 짝수만 포함하도록 n개의 요소 목록을 필터링합니다. n개의 요소가 모두 홀수인 최악의 경우 함수는 n개의 요소를 모두 반복해야 하므로 O(n) 시간 복잡도가 발생합니다.

이러한 예제는 모두 O(n) 시간 복잡도를 가집니다. 알고리즘에 걸리는 시간이 입력 크기(즉, 목록의 요소 수)에 정비례하기 때문입니다.

O(n^2): 이것은 2차 시간 복잡도를 나타내며, 이는 알고리즘이 작업을 완료하는 데 걸리는 시간이 입력 크기의 제곱에 따라 증가함을 의미합니다. 예를 들어 동일한 배열에서 반복되는 중첩 루프는 O(n^2) 시간 복잡도입니다.

 

버블 정렬:

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

행렬

def matrix_multiply(A, B):
    n = len(A)
    C = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

이 함수는 각 행렬의 행과 열을 반복하고 해당 요소의 곱을 합산하여 두 개의 n x n 행렬을 곱합니다. 행렬이 가득 차고 모든 요소가 0이 아닌 최악의 경우 함수는 n^3 연산을 수행해야 하므로 O(n^2) 시간 복잡도가 발생합니다.

 

선택 정렬:

def selection_sort(my_list):
    n = len(my_list)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if my_list[j] < my_list[min_idx]:
                min_idx = j
        my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
    return my_list

이 함수는 선택 정렬 알고리즘을 사용하여 n개의 요소 목록을 정렬합니다. 목록의 정렬되지 않은 부분에서 가장 작은 요소를 찾아 정렬되지 않은 부분의 첫 번째 요소와 교체하고 완전히 정렬될 때까지 목록을 여러 번 반복합니다. 목록이 역순인 최악의 경우 함수는 n*(n-1)/2 비교 및 ​​교환을 수행해야 하므로 O(n^2) 시간 복잡도가 발생합니다.

이러한 예제는 모두 O(n^2) 시간 복잡도를 가집니다. 왜냐하면 알고리즘에 걸리는 시간은 입력 크기(즉, 목록의 요소 수 또는 행렬 크기)에 따라 기하급수적으로 증가하기 때문입니다.

O(log n): 이는 대수 시간 복잡도를 나타내며, 이는 알고리즘이 작업을 완료하는 데 걸리는 시간이 입력 크기에 따라 대수적으로 증가함을 의미합니다. 예를 들어 이진 검색은 O(log n) 시간 복잡도입니다.

병합 정렬 및 퀵 정렬과 같은 정렬 알고리즘에서 흔히 볼 수 있는 n log n 시간 복잡도를 나타냅니다.

 

이진 검색:

def binary_search(my_list, target):
    low = 0
    high = len(my_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if my_list[mid] == target:
            return mid
        elif my_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

이 함수는 대상 값을 찾기 위해 n개의 요소로 구성된 정렬된 목록에서 이진 검색을 수행합니다. 목표 값을 찾거나 검색 구간이 비게 될 때까지 반복적으로 검색 구간을 반으로 나눕니다. 대상 값이 목록에 없는 최악의 경우 함수는 log2(n) 비교를 수행해야 하므로 O(log n) 시간 복잡도가 발생합니다.

제곱에 의한 지수화:

def pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        y = pow(x, n//2)
        return y*y
    else:
        y = pow(x, (n-1)//2)
        return x*y*y

이 함수는 제곱 알고리즘에 의한 지수화를 사용하여 숫자 x의 n승의 거듭제곱을 계산합니다. 반복적으로 x를 제곱하고 n이 0 또는 1이 될 때까지 n을 2로 나눈 다음 결과를 반환합니다. n이 2의 거듭제곱인 최악의 경우 함수는 log2(n) 곱셈을 수행해야 하므로 O(log n) 시간 복잡도가 발생합니다.

 

병합 정렬:

def merge_sort(my_list):
    if len(my_list) > 1:
        mid = len(my_list) // 2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

이 함수는 병합 정렬 알고리즘을 사용하여 목록을 반으로 재귀적으로 나누고 각 반을 정렬한 다음 정렬된 반쪽을 병합하여 n개의 요소 목록을 정렬합니다. 목록이 완전히 정렬되지 않은 최악의 경우 함수는 log2(n) 병합을 수행해야 하므로 O(log n) 시간 복잡도가 발생합니다.

이러한 예제는 모두 O(log n) 시간 복잡도를 가집니다. 알고리즘에 걸리는 시간이 입력 크기(즉, 목록의 요소 수 또는 지수 크기)에 따라 대수적으로 증가하기 때문입니다.
이것은 가능한 많은 Big O 표기법의 몇 가지 예일 뿐입니다. Big O 표기법의 목적은 입력 크기 측면에서 알고리즘의 시간 복잡도를 측정하는 방법을 제공하여 다양한 알고리즘을 비교하고 주어진 문제에 대해 가장 효율적인 알고리즘을 선택할 수 있도록 하는 것입니다.