[CS] 알고리즘의 복잡도 (시간 복잡도)

2024. 9. 26. 12:04·Minding's Programming/Knowledge
728x90
반응형

알고리즘의 복잡도는 알고리즘의 성능을 평가하는 중요한 척도 중 하나이다. 이 글에서는 시간 복잡도와 공간 복잡도 중 시간 복잡도에 대해서만 간단히 정리한다.

 

시간 복잡도

  • 알고리즘이 실행되는 데 걸리는 시간
  • Big O 표기법을 사용하여 표현 ex) O(n), O(log n), O(n²) 등.
  • 입력 크기에 따른 연산 횟수의 증가율을 나타냄

 

예시

O(1) - 상수 시간 복잡도: 연산 횟수가 입력 크기와 관계없이 일정한 경우

def get_first_element(arr):
    return arr[0] if arr else None

# 사용 예시
print(get_first_element([1, 2, 3, 4, 5]))  # 출력: 1

 

배열의 크기와 관계 없이 첫 번째 원소를 반환하는 함수이므로 일정하다.

 

O(n) - 선형 시간 복잡도: 연산 횟수가 입력 크기에 비례하여 증가하는 경우

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

# 사용 예시
print(linear_search([1, 3, 5, 7, 9], 5))  # 출력: 2

선형 탐색의 예시로 처음부터 하나씩 탐색하는 방식이므로 입력 크기에 비례해 증가한다.

 

O(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

# 사용 예시
print(binary_search([1, 3, 5, 7, 9], 7))  # 출력: 3

이진 탐색의 예시로, 검색 때 마다 범위를 반으로 줄이므로 O(log n)의 복잡도를 가진다.

 

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

# 사용 예시
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))  # 출력: [11, 12, 22, 25, 34, 64, 90]

이중 반복문을 사용하는 버블 정렬의 예시로, 입력 크기의 제곱에 비례한 시간이 소요된다.

 

 

728x90

'Minding's Programming > Knowledge' 카테고리의 다른 글

[CS/Python] 자료구조 & 알고리즘 정리 - 큐, 트리, 힙  (0) 2024.09.27
[CS/Python] 자료구조 & 알고리즘 정리 - 연결 리스트, 스택, 후위 표기법  (0) 2024.09.26
[CS/Python] 자료구조 & 알고리즘 정리 - 선형 배열, 정렬, 탐색, 재귀, 순열  (1) 2024.09.26
[Linux/WSL] 간단한 리눅스 명령어 정리  (0) 2024.07.18
카카오톡 메시지로 긍/부정어 감정 분석해보기 (재미로 보는 야구팬들의 감정 분석)  (0) 2024.07.15
'Minding's Programming/Knowledge' 카테고리의 다른 글
  • [CS/Python] 자료구조 & 알고리즘 정리 - 큐, 트리, 힙
  • [CS/Python] 자료구조 & 알고리즘 정리 - 연결 리스트, 스택, 후위 표기법
  • [CS/Python] 자료구조 & 알고리즘 정리 - 선형 배열, 정렬, 탐색, 재귀, 순열
  • [Linux/WSL] 간단한 리눅스 명령어 정리
Minding
Minding
  • Minding
    Today's Minding
    Minding
  • 전체
    오늘
    어제
    • 울고넘는 딥러닝 (278)
      • Minding's Baseball (57)
        • MLB Statcast (29)
        • 머신러닝으로 홈런왕 예측하기 (3)
        • 야구칼럼 (12)
        • 야구 규칙, 용어 (1)
        • 2022-23 질롱 코리아 (8)
        • 류현진 등판경기 (4)
      • Minding's Programming (185)
        • 프로그래머스 코딩테스트 (21)
        • Knowledge (44)
        • Numpy & Pandas (6)
        • Excel (3)
        • Git (1)
        • Pygame (11)
        • CV (3)
        • Tensorflow tutorial (4)
        • Kaggle and Dacon (4)
        • 에러 코드 (8)
        • FastAPI (8)
        • Airflow (29)
        • Crawling (6)
        • Django (14)
        • AWS (18)
        • Spark (5)
      • Minding's Reading (30)
        • 머신러닝 딥러닝에 필요한 기초 수학 with 파이.. (2)
        • 칼만필터는 어렵지 않아 (11)
        • 밑바닥부터 시작하는 딥러닝 (6)
        • 메이저리그 야구 통계학 2e (8)
        • 논문읽기 (2)
        • 빅데이터를 지탱하는 기술 (1)
      • Minding's Life (5)
        • 주식 (4)
        • 각종 소식 (1)
  • 블로그 메뉴

    • 홈
    • Baseball
    • Programming
    • Reading
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    KBO
    Airflow
    MLB
    파이썬
    프로그래머스
    칼만필터는어렵지않아파이썬
    코딩테스트
    야구
    KalmanFilter
    칼만필터
    mlb stats api
    질롱코리아
    FastAPI
    칼만필터는어렵지않아python
    데이터분석
    에어플로우
    django python
    파이게임
    게임개발
    머신러닝
    딥러닝
    django
    파이썬게임개발
    데이터 엔지니어
    AWS
    넘파이
    pygame
    칼만필터는어렵지않아
    메이저리그
    Python
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Minding
[CS] 알고리즘의 복잡도 (시간 복잡도)
상단으로

티스토리툴바