[Python] 알고리즘 개념1 - 시간복잡도 & 공간복잡도

 

 

📘 1. 시간복잡도(Time Complexity)란?

 

📌 시간복잡도란?

시간복잡도는 알고리즘이 실행되는 데 걸리는 시간을 분석하는 방법입니다. 입력 크기(nn)가 커질 때, 실행 시간이 어떻게 변하는지를 나타냅니다.
예를 들어, nn개의 숫자를 더하는 알고리즘이 있다면:

sum = 0
for i in range(n):
    sum += i

이 코드의 실행 시간은 O(n)O(n) 입니다.

 

📌 Big-O 표기법 (빅오 표기법)

Big-O 표기법은 최악의 경우를 기준으로 알고리즘의 수행 시간을 표현하는 방법입니다. 대표적인 시간복잡도는 다음과 같습니다.
표기법 설명 예제

O(1)O(1)	입력 크기에 상관없이 항상 일정한 시간	리스트의 첫 번째 원소 접근 arr[0]
O(n)O(n)	입력 크기에 비례하는 시간	리스트 순회 for i in arr:
O(n2)O(n^2)	중첩 반복문이 있는 경우	버블 정렬
O(logn)O(log n)	입력 크기가 절반씩 줄어드는 경우	이진 탐색
O(n!)O(n!)	모든 경우의 수를 다 고려하는 경우	순열 생성

예제 코드: O(1)O(1), O(n)O(n), O(n2)O(n^2) 비교

# O(1): 항상 일정한 시간
arr = [1, 2, 3, 4, 5]
print(arr[0])  # 첫 번째 원소 접근 (항상 한 번 실행)

# O(n): 리스트 순회
for num in arr:
    print(num)  # 리스트 크기만큼 실행됨

# O(n^2): 중첩 반복문
for i in range(len(arr)):
    for j in range(len(arr)):
        print(i, j)  # 리스트 크기의 제곱만큼 실행됨

---

 

 

📘 2. 공간복잡도(Space Complexity)란?

 

📌 공간복잡도란?

공간복잡도는 알고리즘이 실행될 때 얼마나 많은 메모리를 사용하는지를 나타냅니다. 주로 입력 데이터 크기(nn)에 따라 변하는 메모리 사용량을 측정합니다.

 

📌 공간복잡도 예제

공간복잡도 설명 예제

O(1)O(1)	추가 메모리를 거의 사용하지 않음	단순 변수 선언 x = 10
O(n)O(n)	입력 크기만큼 추가 공간 필요	리스트 저장 arr = [0] * n
O(n2)O(n^2)	2차원 리스트를 사용하는 경우	matrix = [[0]*n for _ in range(n)]

 
예제 코드:

# O(1) 공간복잡도: 변수 하나만 사용
x = 10  # 추가 메모리 사용 없음

# O(n) 공간복잡도: 리스트 사용
arr = [0] * n  # 입력 크기만큼 메모리 필요

# O(n^2) 공간복잡도: 2차원 리스트 사용
matrix = [[0] * n for _ in range(n)]  # n x n 크기의 리스트 생성

---

 

 

📘 3. 실행 시간 측정 방법

파이썬에서 코드의 실행 시간을 측정하는 방법은 time 모듈을 사용하는 것입니다. 아래 예제는 특정 코드 블록의 실행 시간을 측정하는 방법을 보여줍니다:

import time

start = time.time()  # 시작 시간 기록

# 실행할 코드
sum = 0
for i in range(1000000):
    sum += i

end = time.time()  # 종료 시간 기록
print(f"실행 시간: {end - start:.10f}초")

이 방법을 사용하면 알고리즘이 얼마나 빠르게 실행되는지 측정할 수 있습니다. 😊