[Algorithm] 복잡도 (Complexity)

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다.

복잡도 (Complexity)

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

복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.

시간 복잡도는 알고리즘을 위해 필요한 연산의 횟수이다. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미하한다.

공간 복잡도는 알고리즘을 위해 필요한 메모리의 양이다. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

시간 복잡도와 공간 복잡도 간의 거래 관계 (Trade-off)

효율적인 알고리즘을 사용한다고 가정했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(Trade-off)가 성립한다.

메모리를 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션(Memoization) 기법이 있다.

빅오 표기법 (Big-O Notation)

시간 복잡도나 공간 복잡도를 표현할 때 빅오(Big-O) 표기법을 사용한다. 빅오 표기법을 간단히 정의하면 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다.