[Algorithm] 복잡도 (Complexity)

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다. 복잡도 (Complexity) 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다. 시간 복잡도는 알고리즘을 위해 필요한 연산의 횟수이다. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미하한다. 공간 복잡도는 알고리즘을 위해 필요한 메모리의 양이다. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 시간 복잡도와 공간 복잡도 간의 거래 관계 (Trade-off) 효율적인 알고리즘을 사용한다고 가정했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 ..