잠깐만요

계산 복잡도: 시간 복잡도와 공간 복잡도

계산 복잡도에는 계산을 얼마나 빨리 할 수 있는지 따져 보는 ‘시간 복잡도’와 계산에 얼마나 많은 저장 공간이 필요한지 따져 보는 ‘공간 복잡도’가 있습니다. 앞에서는 주로 시간 복잡도만 생각해 볼 것이라고 했습니다.

딕셔너리를 이용해 동명이인을 찾는 문제는 모든 사람을 서로 비교하는 방법보다 더 나은 시간 복잡도를 가집니다. 하지만 딕셔너리를 만들어 그 안에 모든 이름과 등장 횟수를 저장해야 하므로 더 많은 저장 공간을 사용합니다. 이것은 공간 복잡도를 희생하여 시간 복잡도를 개선한 것이라고 생각할 수 있습니다.

알고리즘 분석을 정확하게 하려면 시간 복잡도뿐만 아니라 공간 복잡도도 함께 고려해야 합니다. 하지만 현대 컴퓨터는 대체로 저장 공간(메모리, 하드디스크)이 매우 크기 때문에 상대적으로 공간 복잡도에 덜 민감한 편입니다.