3. 계산 복잡도 (시간복잡도,공간복잡도) 정리
알고리즘 공부
2019. 9. 21.
계산 복잡도 (Computational Complexity) 계산 복잡성, 계산 효율성, 알고리즘 효율성, Time Complexity, 시간 복잡도, 빅 오 표기법 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리듬이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 공간 복잡도라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. https://ko.wikipedia.org/wiki/계산_복잡도_이론 계산 복잡도 이론 ..
