시간복잡도와 공간복잡도

마동찬·2023년 8월 14일

취업대비

시간복잡도

💡 시간 복잡도(Time Complexity)

알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미합니다.
즉, 입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지에 따른 지표입니다.
시간 복잡도는 ‘빅오 표기법(Big-O notation)’를 통해 표현하며 수치가 작을수록 효율적인 알고리즘을 의미합니다.

💡 시간복잡도를 줄이는법

정렬된 배열 arr에서 특정 원소의 위치를 찾는 문제를 생각해봅시다. 배열의 모든 원소를 순회한다면 이는 O(N)의 시간 복잡도가 소요됩니다. 하지만 정렬되어 있다는 조건에 주목하면 이후에 살펴볼 이진 탐색을 적용할 수 있다는 것을 알 수 있습니다. 이진 탐색의 시간 복잡도는 O(logN)이므로 훨씬 효율적으로 탐색할 수 있습니다.
또 배열에서 중복을 제거한 원소들을 찾고 싶을 때 원소별로 배열 전체를 순회하면 O(N2)의 시간 복잡도가 소요됩니다. 이때는 자료 구조 Set을 이용하면 O(N)으로 해결할 수 있습니다. O(N2)과 O(N)은 N의 크기가 커질수록 엄청난 효율성 차이를 보입니다.

공간 복잡도

💡 공간 복잡도(Space Complexity)란?

알고리즘이 실행될 때 필요한 ‘메모리 공간의 양’을 의미합니다.
즉 알고리즘의 효율성을 판단하는 데 사용되며 일반적으로 메모리 사용량이 적을수록 더 효율적인 알고리즘이라고 할 수 있습니다.
공간 복잡도는 일반적으로 알고리즘의 시간 복잡도와 함께 고려되며 알고리즘이 실행되는 환경에 따라 달라질 수 있습니다. 예를 들어, 일부 알고리즘은 실행될 때 추가적인 메모리를 필요로 하지 않지만 다른 알고리즘은 입력 데이터의 양에 따라 필요한 메모리 공간이 증가할 수 있습니다.
따라서 알고리즘을 설계할때에는 시간 복잡도와 공간 복잡도를 함께 고려해야 합니다.

💡 공간복잡도를 줄이는법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.

프로그램에 필요한 공간은 크게 두가지로 나눌 수 있습니다.

고정 공간
가변 공간

시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적입니다. 또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에 만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로 짜는게 더 효율적이라고 볼 수 있습니다.