지니 코딩일기

제대로 된 알고리즘을 구현하기 위해서는 복잡도를 고려해야 한다. 복잡도에 대해 알아보자. 복잡도 복잡도(complexity) : 알고리즘의 성능을 나타내는 척도 - 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 -> 필요한 연산의 횟수 - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 -> 필요한 메모리의 양 => 동일한 기능을 수행한다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도 - 시간제한 내에 구현하여야 함 (보통 1~5초 제한) - Big-O 표기법 사용 (가장 빠르게 증가하는 항만을 고려하는 표기) - 최악인 경우의 시간복잡도를 우선 고려하여야 함 - 보통의 경우 상수항을 무시하지만, 항상 절대적인 것은 아님 ..