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

2024-10-25 16:25:58 | 조회수 40


1. 빅 오 표기법 개요

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

빅 오 표기법의 주요 목적

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

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

주요 시간 복잡도 유형

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

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

주요 공간 복잡도 유형

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

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

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

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

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

이번 글에서는 알고리즘의 효율성을 평가할 때 사용하는 빅 오 표기법시간 복잡도 및 공간 복잡도 개념을 다뤄보았습니다. 알고리즘을 작성할 때, 복잡도 평가를 통해 더 효율적인 해결책을 찾아보세요!


빅 오 표기법: 시간 복잡도와 공간 복잡도 - 알고리즘닷컴 19 개의 글