[개념] 복잡도(Complexity)

Big-O notation

 

이미지 출처: https://www.scholarhat.com/tutorial/datastructures/complexity-analysis-of-data-structures-and-algorithms

 

정의: 알고리즘의 성능을 나타내는 척도

종류: 시간 복잡도, 공간(메모리) 복잡도

* 일반적으로 복잡도라고 하면 시간 복잡도를 의미한다.

표기 방법: 빅오 표기법

* 빅오(Big-O) 표기법이란, 구현한 알고리즘을 시간 혹은 메모리에 대한 함수로 나타낸 후, 그 함수의 상한만을 고려한 표기방식이다.

주의 사항: 소스 코드를 정확히 분석하여 복잡도를 계산하여야 한다. 만약 내부적으로 함수를 호출한다면 내부 함수도 복잡도를 계산해주어야 한다.

코딩 테스트 시 제한 기준 (일반적인 상황)

- 시간 복잡도: 1초, O(N^3)

- 공간 복잡도: 128~512MB

 

수행 시간 측정 방법

import time

start_time = time.time()

```
시간 측정할 알고리즘
```

end_time = time.time()

print("소요 시간(초):", end_time - start_time)