이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
컴퓨터 과학에서 공간 복잡도는 알고리즘이 입력 길이의 함수로 실행하는 데 필요한 메모리의 양입니다. 공간 복잡도는 종종 O(log n), O(n), O(n log n), O(n^2) 또는 O(2^n)과 같은 점근적 표기법으로 표현됩니다.
알고리즘의 공간 복잡도는 입력 길이의 함수로 알고리즘을 실행하는 데 필요한 메모리 양입니다. 공간 복잡도는 종종 O(log n), O(n), O(n log n), O(n^2) 또는 O(2^n)과 같은 점근적 표기법으로 표현됩니다.
알고리즘의 공간 복잡도를 계산하려면 알고리즘이 사용하는 정적 공간과 동적 공간을 모두 고려해야 합니다.
정적 공간은 입력 크기에 관계없이 알고리즘에 필요한 공간의 양입니다. 여기에는 프로그램 코드와 알고리즘이 사용하는 모든 정적 데이터 구조에 필요한 공간이 포함됩니다.
동적 공간은 입력 크기가 증가함에 따라 알고리즘에 필요한 공간의 양입니다. 여기에는 스택, 대기열 및 트리와 같이 알고리즘이 사용하는 동적 데이터 구조에 필요한 공간이 포함됩니다.
알고리즘의 총 공간 복잡도는 정적 공간과 동적 공간의 합입니다.
다음은 공간 복잡도 계산의 몇 가지 예입니다.
알고리즘을 실행하는 데 필요한 공간의 양이 입력 크기와 무관한 경우 알고리즘은 일정한 공간 복잡도를 갖는다고 합니다.
공간 복잡도가 일정한 알고리즘의 좋은 예는 두 개의 숫자를 더하는 것입니다. 두 숫자를 저장하는 데 필요한 공간의 양은 숫자의 크기와 무관합니다.
알고리즘을 실행하는 데 필요한 공간의 양이 입력 크기의 대수인 경우 알고리즘이 대수 공간 복잡도를 갖는다고 합니다.
로그 공간 복잡도가 있는 알고리즘의 좋은 예는 이진 검색입니다. 이진 검색을 수행하려면 입력 배열을 메모리에 저장해야 합니다. 그러나 배열을 저장하는 데 필요한 공간의 양은 입력 크기의 대수입니다.
알고리즘을 실행하는 데 필요한 공간의 양이 입력 크기에 비례하는 경우 알고리즘은 선형 공간 복잡도를 갖는다고 합니다.
선형 공간 복잡성이 있는 알고리즘의 좋은 예는 선형 검색입니다. 선형 검색을 수행하려면 입력 배열을 메모리에 저장해야 합니다. 배열을 저장하는 데 필요한 공간의 양은 입력 크기에 비례합니다.
알고리즘을 실행하는 데 필요한 공간의 양이 입력 크기에서 n log n이면 알고리즘이 n log n 공간 복잡도를 갖는다고 합니다.
n log n 공간 복잡도를 갖는 알고리즘의 좋은 예는 병합 정렬입니다. 병합 정렬을 수행하려면 입력 배열을 메모리에 저장해야 합니다. 배열을 저장하는 데 필요한 공간의 양은 입력 크기의 n log n입니다.
알고리즘을 실행하는 데 필요한 공간의 양이 입력 크기에서 2차인 경우 알고리즘이 2차 공간 복잡도를 갖는다고 합니다.
2차 공간 복잡도가 있는 알고리즘의 좋은 예는 버블 정렬입니다. 버블 정렬을 수행하려면 입력 배열을 메모리에 저장해야 합니다. 배열을 저장하는 데 필요한 공간의 양은 입력 크기의 2차입니다.
알고리즘을 실행하는 데 필요한 공간의 양이 입력 크기에서 기하급수적이면 알고리즘이 기하급수적 공간 복잡도를 갖는다고 합니다.
기하급수적인 공간 복잡도를 가진 알고리즘의 좋은 예는 무차별 대입 검색입니다. 무차별 대입 검색을 수행하려면 입력 배열을 메모리에 저장해야 합니다. 배열을 저장하는 데 필요한 공간의 양은 입력 크기에 따라 기하급수적으로 증가합니다.