Big O 표기법

기본 개념

1. 알고리즘: 문제를 해결하는 절차나 방법
2. 시간 복잡도: 알고리즘이 실행되는 데 걸리는 시간으로 데이터의 크기에 따라 처리하는 시간이 얼마나 늘어나는지를 나타냄. (https://gangdonggil.tistory.com/80)
3. Big O 표기법: 시간 복잡도를 표현하는 표기법으로 **데이터의 크기(n)**에 따라 시간이나 공간이 어떻게 변하는지 나타낸다.

Big O 표기법의 예시 (소스코드 ChatGPT 생성)

1. O(1): 상수 시간 복잡도. 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘.

def get_first_element(arr):
    return arr[0]

2. O(n): 선형 시간 복잡도. 데이터의 크기(n)가 커지면 걸리는 시간도 비례해서 커진다.

def print_all_elements(arr):
    for element in arr:
        print(element)

3. O(n^2): 이차 시간 복잡도. 데이터의 크기가 커질수록 시간이 제곱으로 늘어난다.

def print_all_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

4. O(log n): 로그 시간 복잡도. 데이터의 크기가 늘어도 처리하는 시간의 증가하는 속도(log n)가 매우 낮다.

def binary_search(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