복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다.

 

 

 

 

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

 

 

동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

 

소스코드가 길고 많은 모듈이 있는 경우 코드가 복잡하다고 할 수 있는데 여기서 단순히 코드가 복잡한건 복잡도가 아니다. 성능적인 부분이 중요한 것임.

 

 

시간복잡도가 낮으면 더 빠르게 실행 가능한 것.

공간복잡도 낮으면 더 적은 메모리로 실행 가능한 것.

빅오 표기법

사진 출처: 유튜브 동빈나

 

가장 빠르게 증가하는 항만을 고려하는 표기법.

 

빅오 표기법에서는 차수가 가장 큰 항만 남긴다. 최고차항을 보는 것.

 

 

 

일반적으로 빅오 표기법은 알고리즘의 최악의 경우(worst-case)를 기준으로 한다.

 

최악의 경우에 대한 이해는 알고리즘의 안정성을 평가하고 예상 가능성을 제공하는 데 도움이 된다.

 

하지만 최악의 경우뿐만 아니라 최선의 경우나 평균적인 경우에 대해서도 알고리즘의 성능을 고려해야 한다.

 

종종 알고리즘의 최악의 경우가 실제로 발생할 가능성이 매우 낮거나 드문 경우가 있을 수 있기 때문.

 

 

import time

start_time = time.time() # 측정 시작

#프로그램 소스코드
end_time = time.time() #측정 종료
print("time: ", end_time - start_time) # 수행 시간 출력