복잡도는 알고리즘의 성능을 나타내는 척도이다.
시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.
소스코드가 길고 많은 모듈이 있는 경우 코드가 복잡하다고 할 수 있는데 여기서 단순히 코드가 복잡한건 복잡도가 아니다. 성능적인 부분이 중요한 것임.
시간복잡도가 낮으면 더 빠르게 실행 가능한 것.
공간복잡도 낮으면 더 적은 메모리로 실행 가능한 것.
빅오 표기법

사진 출처: 유튜브 동빈나
가장 빠르게 증가하는 항만을 고려하는 표기법.
빅오 표기법에서는 차수가 가장 큰 항만 남긴다. 최고차항을 보는 것.
일반적으로 빅오 표기법은 알고리즘의 최악의 경우(worst-case)를 기준으로 한다.
최악의 경우에 대한 이해는 알고리즘의 안정성을 평가하고 예상 가능성을 제공하는 데 도움이 된다.
하지만 최악의 경우뿐만 아니라 최선의 경우나 평균적인 경우에 대해서도 알고리즘의 성능을 고려해야 한다.
종종 알고리즘의 최악의 경우가 실제로 발생할 가능성이 매우 낮거나 드문 경우가 있을 수 있기 때문.
import time
start_time = time.time() # 측정 시작
#프로그램 소스코드
end_time = time.time() #측정 종료
print("time: ", end_time - start_time) # 수행 시간 출력
'Algorithm > 알고리즘' 카테고리의 다른 글
| [백준/자바] 1260번 - DFS와 BFS 구현하기 (3) | 2025.01.17 |
|---|---|
| [백준/자바] 1157 - 단어 공부 (1) | 2025.01.16 |
| [백준/파이썬] 28278 (0) | 2024.11.10 |
| 함수와 재귀함수(Python) (2) | 2024.05.20 |
| 알고리즘에 도움되는 간단한 파이썬 문법 (1) | 2024.05.12 |