알고리즘에서 '시간복잡도'와 '공간복잡도'란

시간복잡도

해당 알고리즘이 실행되는 데 걸리는 시간의 총량을 나타낸다.

---

 '빅오(Big-O)' 표기법을 사용하여 표현되며 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 수학적인 표기법으로, 알고리즘의 최악의 실행 시간을 나타낸다.

예를 들어, 배열에서 항목을 검색하는 선형 검색 알고리즘의 시간복잡도는 O(n)이며, n은 배열의 크기이다. 이는 최악의 경우에는 배열의 모든 항목을 한 번씩 검색해야 하므로, 입력 크기 n에 비례하여 실행 시간이 증가한다는 것을 의미한다.

반면에, 이진 검색 알고리즘의 시간복잡도는 O(log n)이며, 이는 최악의 경우에도 배열을 계속 절반으로 나누면서 검색을 수행하기 때문에, 입력 크기 n에 비례하여 실행 시간이 더욱 적게 증가한다는 것을 의미한다.

---

공간복잡도

해당 알고리즘이 실행될 때 필요로 하는 메모리 공간의 양을 나타낸다.
즉, 알고리즘이 동작하기 위해 컴퓨터 메모리에서 사용되는 공간의 총량을 의미한다.

---

공간복잡도는 대개 알고리즘의 입력 크기에 따라 변하지 않으며,
알고리즘 내에서 사용되는 변수, 배열, 스택, 큐 등의 자료구조와 함수 호출에 의해 결정된다.

---

'빅오(Big-O)' 표기법을 사용하여 표현되며 입력 크기에 따라 알고리즘이 필요로 하는 최대 메모리 공간을 표현하게 된다.

예를 들어, 배열을 정렬하는 선택 정렬 알고리즘의 공간복잡도는 입력 배열을 복사하여 정렬하는 추가적인 배열이 필요하기 때문에 O(n)이다.

반면에, 퀵 정렬 알고리즘의 공간복잡도는 재귀호출에 필요한 스택 공간의 크기 때문에 일반적으로 O(log n)이다,