공간복잡도
-
[추가] 복잡도Algorithm/개념정리 2021. 7. 9. 10:58
복잡도?! 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도 시간복잡도 + 공간복잡도 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 → 알고리즘을 위해 필요한 연산 횟수 측정 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 → 알고리즘을 위해 필요한 메모리의 양 측정 → 둘은 일종의 거래 관계가 성립함 → 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하는 등 → 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법을 '메모이제이션' 기법이라고 함 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도 알고리즘 문제 풀 때 단순히 '복잡도'는 시간 복잡도를 의미함 시간복잡도 표현 시 '빅오(Big-O) 표기법'을 사용함 →..