빅 오 표기법: 시간 복잡도와 공간 복잡도

빅 오 표기법(Big-O Notation)은 알고리즘의 효율성을 나타내는 방법으로, 주어진 입력 크기에 대해 알고리즘이 얼마나 빠르게 실행되는지를 표현합니다. 일반적으로 가장 큰 입력 크기(N)에 대해 알고리즘의 성능이 어떻게 변하는지 평가할 때 사용합니다.

빅 오 표기법의 주요 목적

• 시간 복잡도: 알고리즘이 주어진 입력 크기에 대해 얼마나 빠르게 실행되는지를 나타냄
• 공간 복잡도: 알고리즘이 주어진 입력 크기에 대해 얼마나 많은 메모리를 사용하는지를 나타냄

시간 복잡도는 **입력 크기(N)**에 따라 알고리즘이 실행되는 데 걸리는 시간을 나타냅니다. 알고리즘의 주요 연산 횟수를 빅 오 표기법으로 표현하여 알고리즘의 효율성을 평가합니다.

주요 시간 복잡도 유형

• O(1): 상수 시간 복잡도, 입력 크기에 상관없이 일정한 시간이 소요됨 (예: 배열의 인덱스를 통한 접근)
• O(log N): 로그 시간 복잡도, 이진 탐색과 같이 입력 크기가 커질수록 시간이 조금씩 증가
• O(N): 선형 시간 복잡도, 입력 크기에 비례하여 시간이 증가 (예: 배열의 모든 요소를 한 번씩 탐색)
• O(N log N): 선형 로그 시간 복잡도, 효율적인 정렬 알고리즘(예: 병합 정렬)
• O(N^2): 이차 시간 복잡도, 중첩 루프가 포함된 알고리즘 (예: 버블 정렬)

공간 복잡도는 **입력 크기(N)**에 따라 알고리즘이 사용하는 메모리 양을 나타냅니다. 공간 복잡도를 줄이면 더 적은 메모리를 사용하여 효율적인 실행이 가능해집니다.

주요 공간 복잡도 유형

• O(1): 상수 공간 복잡도, 입력 크기와 관계없이 일정한 메모리 사용
• O(N): 선형 공간 복잡도, 입력 크기에 비례하는 메모리 사용
• O(N^2): 이차 공간 복잡도, 중첩 구조로 인해 메모리 사용량이 급격히 증가

문제 설명: 주어진 배열에서 모든 요소를 더하는 알고리즘의 시간 복잡도와 공간 복잡도를 평가하세요.

Python 코드 예제:
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total
                

시간 복잡도: O(N), 배열의 모든 요소를 순회하므로 입력 크기 N에 비례해 시간이 증가합니다.

공간 복잡도: O(1), 추가 메모리 사용이 거의 없으므로 일정한 공간 복잡도를 가집니다.