복잡도
복잡도의 정의
복잡도는 알고리즘의 성능을 나타내는 척도로 시간 복잡도(Time Complexity)와, 공간 복잡도(Space Complexity)로 나눌 수 있다.
시간 복잡도(Time Complexity)
- 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.
- 시간 복잡도를 측정함으로써 알고리즘을 위해 필요한 연산의 횟수를 계산할 수 있다.
- 시간 복잡도를 표현할 때에는 주로 Big-O 표기법을 사용하는데, Big-O 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
- 일반적으로 평균 시간 복잡도와 최악 시간 복잡도를 모두 고려해보아야 하며, 코딩 테스트에서 알고리즘을 작성할 때에는 최악 시간 복잡도를 우선적으로 고려해야한다.
공간 복잡도(Space Complexity)
- 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
- 공간 복잡도를 측정함으로써 알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다.
- 공간 복잡도를 표현할 때에도 주로 Big-O 표기법을 사용한다.
참고자료
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈
개발하는 강아지