컴퓨터 공학/알고리즘
(알고리즘) Big-O, 시간복잡도와 공간 복잡도
알고리즘의 시간과 공간을 측정할 때는 시간복잡도와 공간 복잡도라는 말을 많이 쓴다. 그런데 시간 복잡도는 무엇이며, 공간 복잡도는 무엇일까? 시간 복잡도는 '어떤 일을 수행할 때, 그 일이 완료되기까지 걸리는 시간이 얼마나 복잡한가' 라고 생각하면 편하다. 공간 복잡도는 '어떤 일을 수행할 때, 그 일이 완료되기까지 필요한 공간(메모리)가 얼마다 되는가' 라고 생각하면 된다. 복잡도의 개념에 대해 알았으면, 이를 표기할 방법이 필요하다. 얼마나 복잡한지를 어떻게 표현할 것인가? (하늘만큼 땅만큼 복잡해요) 이때 Big-O의 개념이 등장한다. 🧐Big-O만 있는게 아니다? 많은 사람들이 시간 복잡도라고 하면 Big-O를 떠올릴 것이다. 하지만 시간복잡도와 공간복잡도를 나타내는 방법에서는 Big-O만 존재하..
