들어가며
이 책 전반에서 다양한 알고리즘의
효율성을 분석하면서
오로지 시간 복잡도에만 초점을
맞췄다.
즉 알고리즘이 얼마나 많은
메모리를 소모하는가로
알고리즘의 효율성을 측정해야
할 때가 있다.
메모리 제한이 있다면 공간 복잡도가
중요한 요인이다.
비교적 적은 양의 메모리만
포함하는
작은 하드웨어 장치를 위한
프로그래밍이나
아주 대량의 데이터가 데이터보다
훨씬 큰 메모리 컨테이너를
빠르게 채우는 상황을 처리할
때 그렇다.
이상적으로는 빠르면서도
메모리를 적게 소비하는
그러한 알고리즘만 사용하고
싶을 것이다.
하지만 빠른 알고리즘은 효율적인
메모리 알고리즘 사이에서
선택해야 하는 상황이 있을
것이고
올바른 선택을 하려면 그러한
상황을 유심히 살펴봐야 한다.
14.1. 공간 복잡도에 빅 오 표기법 적용
흥미롭게도 컴퓨터 과학자는
시간 복잡도를 표현할 때와
마찬가지로 빅 오 표기법을
사용해 공간 복잡도를 표현한다.
지금까지 빅 오 표기법을
사용해 다음과 같은 방식으로
알고리즘의 속도를 표현했다.
데이터 원소가 N개일 때,
알고리즘은 N에 비례하는 연산
단계가 걸린다.
예를 들어 O(N)은 데이터 원소가
N개일 때,
알고리즘에 N단계가 걸린다는
뜻이다.
또한 O(N²)은 데이터 원소가
N개일 때,
알고리즘에 N²단계가 걸린다는
뜻이다.
비슷한 방식으로 빅 오를 사용해
알고리즘에
최대 얼마나 많은 공간이 필요한가를
표현할 수 있다.
데이터 원소가 N개일 때,
알고리즘은 메모리 내 추가로 들어있는
데이터 원소 수에 비례해서 공간을 소모한다.
간단한 예제를 살펴보자.
문자열 배열을 받아 모두 대문자로
바꾼 배열을 반환하는
자바스크립트 함수를 작성한다고 하자.
예를 들어 이 함수는
["amy", "bob", "cindy", "derek"]
위와 같은 배열을 받아
["AMY", "BOB", "CINDY", "DEREK"]
을 반환한다.
다음은 이러한 함수를 작성하는
한 가지 방법이다.
function makeUpperCase(array) {
var newArray = [];
for(var i=0; i<array.length; i++){
newArray[i] = array[i].toUpperCase();
}
return newArray;
}
makeUpperCase() 함수는 array라는
배열을 받는다.
이어서 newArray라는 완전히
새로운 배열을 생성해서
원래 배열의 각 문자열을 대문자로
바꿔 채운다.
함수가 끝났을 때 컴퓨터 메모리에는
두 배열이 들어 있다.
["amy", "bob", "cindy", "derek"]
을 포함하는 array와
["AMY", "BOB", "CINDY", "DEREK"]
을 포함하는 newArray다.
위 함수를 공간 복잡도 관점에서
분석하면
원소 N개를 받아 마찬가지로
원소 N개인 새로운 배열을 생성한다.
따라서 makeUpperCase() 함수의
공간 효율성은 O(N)이다.
이를 그래프로 나타내는 방식은
다음 그래프처럼
우리에게 꽤 익숙하다.
(그림)
위 그래프는 세로축이 속도가
아닌 메모리라는 점만 제외하면
이전 장들에서 그래프로 O(N)을
묘사한 방식과 동일하다.
다음은 메모리 효율적인
makeUpperCase()함수다.
function makeUpperCase(array) {
for(var i=0; i<array.length; i++){
array[i] = array[i].toUpperCase();
}
return array;
}
두 번째 makeUpperCase() 버전은
새 변수나 새 배열을 생성하지 않는다.
사실상 새로운 메모리를 전혀
소비하지 않는다.
대신 원래 array 내에서 한 번에
하나씩 대문자로 바꾸면서
각 문자열을 수정한다.
끝으로 수정된 array를 반환한다.
원래 배열 외에 어떤 메모리도
쓰지 않으므로
위 함수의 공간 복잡도를 O(1)으로
표현한다.
시간 복잡도에서 O(1)은 데이터가
얼마나 크든
알고리즘 속도가 상수라는 뜻이다.
예제 알고리즘 원래 array의 원소가
4개든 100개든
추가로 소비하는 공간이 같다.
즉, 0이다.
따라서 새로운 makeUpperCase()의
공간 효율성은 O(1)이다.
이 책은 보조 공간이라 불리는
추가로 소비되는 메모리에 따라
공간 복잡도를 판단한다는 점을
거듭 강조한다.
즉, 원래 데이터는 포함하지 않는다.
두 번째 makeUpperCase()도
메모리에 저장된 원소가 N개인
array를 입력으로 받는다.
하지만 원래 배열 외에 어떤
메모리도 소비하지 않으므로
공간 복잡도는 O(1)이다.
어떤 책에서는 원래 입력도 초함하여 공강 복잡도를 계산하는데 이렇게 해도 상관 없다. 다만 여기서는 포함하지 않으므로 공간 복잡도가 설명된 자료를 볼 때는 원래 입력을 포함하는지 아닌지 먼저 파악한다.
다음 표에서 두 makeUpperCase()의
시간 복잡도와 공간복잡도를
모두 비교하겠다.
두 버전 모두 데이터 원소가
N개일 때 N단계가 걸리므로
시간 복잡도는 O(N)이다.
하지만 공간 복잡도가 O(N)인
첫 번째 버전에 반해
O(1)인 두 번째 버전이 좀 더
메모리 효율적이다.
이 예제는 버전2가 버전1보다
더 나은, 꽤 확실한 경우다.
14.2. 시간과 공간 트레이드오프
4장 빅 오로 속도 올리기에서
배열에 중복 값이 있는지 확인하는
자바스크립트 함수를 작성했었다.
첫 번째 버전은 다음과 같았다.
function makeUpperCase(array) {
for(var i=0; i<array.length; i++) {
for(var j=0; j<array.length; j++) {
if(i !== j && array[i] == array[j]){
return true;
}
}
}
return false;
}
중첩 for 루프를 사용했으며,
시간 복잡도가 O(N²)이었다.
다음으로 보다 효율적인 버전을
만들었다.
function makeUpperCase(array) {
var existingNumber = [];
for(var i=0; i<array.length; i++) {
if(existingNumber[array[i]] === undefined) {
existingNumber[array[i]] = 1;
}
else {
return true;
}
}
return false;
}
두 번째 버전은 existingNumers라는
배열을 생성하고,
array 내부의 각 수에 대해
existingNumbers 내부의 대응하는
인덱스에
이미 1이 있다면 이 수가 이미
나왔다는 뜻이므로
중복 값을 찾은 것이다.
시간 복잡도가 O(N²)인 첫 번째
버전에 반해
O(N)이므로 두 번째 버전으로
충분하다고 얘기했었다.
확실히 시간 측면만 고려하면
두 번째 버전이 훨씬 빠르다.
하지만 공간을 고려하면 두 번째
버전이
첫 번째 버전에 비해 단점이
있다는 것을 알게 된다.
첫 번째 버전은 원래의 배열 외에
메모리를 추가로 소모하지 않으므로
공간 복잡도가 O(1)이다.
반면 두 번째 버전은 원래 배열과
같은 크기의
완전히 새로운 배열을 생성한다.
따라서 공간 복잡도가 O(N)이다.
다음 표에서는
두 버전의 hasDuplicateValue()를
완벽히 대조하겠다.
Ver.1은 느리지만 메모리를 덜
사용하는 반면
Ver.2는 빠르지만 더 많은 메모리를
사용한다.
어떤 것을 고를지 어떻게 결정할
것인가?
물론 상황에 따라 다르다는 것이
정답이다.
애플리케이션이 매우 빨라야 하고,
처리할 메모리가 충분하다면
Ver.2를 사용하는 것이 낫다.
반대로 속도는 중요하지 않지만
메모리를 절약해야 하는
하드웨어/데이터 조합이라면
Ver.1이 올바른 선택일 수 있다.
모든 기술적인 결정이 그러하듯이
트레이드오프가 있을 때는
전체적인 상황을 봐야 한다.
14.3. 마치면서
지금까지 많은 내용을 배웠다.
무엇보다도 자료 구조와 알고리즘을
분석함으로써
속도와 메모리, 심지어 간결성
면에서
코드에 중대한 영향을 줄 수 있음을
배웠다.
이 책은 숙련된 기술 결정을 내릴
수 있는 프레임워크를 제공한다.
컴퓨팅에는 세부적인 고려사항이
많으므로
빅 오 표기법 등으로
어떤 접근 방식이 다른 접근 방식보다
더 낫다고 제안할 수는 있어도
다른 요인이 충분히 영향을 줄 수 있다.
하드웨어 내에 메모리가 조직되는
방법,
사용자가 고른 커퓨터 언어가
내부적으로 구현된 방법 역시
코드의 효율성에 영향을 줄
수 있다.
사용자가 가장 효율적이라 생각한
결정이
다양한 외부 요인 때문이 아닐
수도 있다.
따라서 벤치마킹 도구를 사용해
항상 사용자가 수행한 최적화를
테스트하는 것이 가장 좋다.
코드 속도와 메모리 소비를
측정할 수 있는
소프트웨어 애플리케이션이
많다.
이 책에 나오는 지식은 당신을
올바른 방향으로 인도할 것이고,
벤치마킹 도구는 당신이 올바른
선택을 했는지 확인해 줄 것이다.
또한 이 책을 통해 이처럼 복잡하고
난해해 보이는 주제가
사실은 더 간단하고 쉬운,
이해할 수 있는 개념들의 조합일
뿐임을 알기 바란다.
어떤 책에 나오는 개념이 어려워
보인다면
그저 잘 설명하지 못한 것이므로
겁먹지 말자.
항상 더 잘 설명한 자료를 찾을
수 있다.
자료 구조와 알고리즘이라는
주제는 넓고 깊으며,
이 책은 수박 겉핥기식으로만
다뤘다.
앞으로 배울 내용이 훨씬 더
많지만
기초를 쌓았으니 충분히 배울
수 있다.
행운을 빈다.
참고 및 출처
 |
|
