프로그래밍 구조와 패턴 1) 시간 복잡도?
Computational Design
일반적으로는 우리가 사용하는 컴퓨터는 순차적(Serial Process)으로 작업을 실행하기 마련인데요. 컴퓨터가 빨라진다는 의미는 이 순차적인 계산을 빨리 한다고 볼 수 있어요. 우리가 보통 CPU의 속도를 이야기할 때, 1기가 헤르즈(GHz), 1.5 혹은 2.0기가 헤르즈(GHz) 등등이라고 이야기하죠.
즉, 이 헤르츠(Hertz)라는 것은, 1초에, 0과 1의 신호가 바뀌는 주기라고 볼 수 있어요. 즉 1Hz는 0과 1을 한 번 실행한다라고 볼 수 있죠!
따라서, 단순 계산을 해보면,
1 킬로 헤르츠(KHz) 즉, 1,000Hz
1 메가헤르츠(MHz) 즉, 1,000KHz 혹은 1,000,000Hz
1 기가헤르츠(GHz) 즉, 1,000 MHz 혹은 1,000,000,000 Hz
1 GHz = 1초에 10억 번의 신호
즉, 1 GHz면 1초에 10억 번의 신호를 바꾸는 속도라고 볼 수 있어요.
제가 사용하는 컴퓨터가 2.6 GHz인데요, 이론상, 26억 번의 연산을 초당 하는 것이죠! 엄청 빠르죠? 물론 2000년도 후반터 물리적인 한계에 이르러 GHz를 높이는 것보다 CPU의 개수를 늘리는 방법과 전력 소로를 줄이는 모바일 쪽으로 발전해오고 있어요.
여하튼, 속도를 측정함에 있어서 여러 가지 요소들이 있는데 우선은 이론적으로 이러하다 정도로 알고 넘어가도 좋을 것 같아요.
여기서 우리가 기억해야 할 것은, 코딩에서의 라인 라인들의 연산에 따라 다소 다르겠지만, 각각의 라인들을 실행할 때, 물리적인 시간이 들어간다는 것이죠.
그래서 코딩을 할 때, 특별히 알고리즘을 작성할 때 이 알고리즘의 성공적인 작동 여부를 떠나서, 이 알고리즘이 컴퓨터의 자원 즉 메모리, 그리고 필요되는 시간을 기준으로 평가를 할 수 있어요.
공간 복잡도 Space Complexity, 그리고 시간 복잡도 Time Complexity
효율적인 알고리즘을 작성하기 위해서 위의 두 가지 요소를 놓고 평가하는데, 특별히 시간 복잡도를 중요시해요. 그 이유는 요즘의 컴퓨터는 메모리가 과거에 비해 용량이 커져서, 시간 복잡도를 더 중요하게 본다고 해요.
그렇다고, 쓸데없는 메모리의 선언을 통해 굳이 긁어서 부스럼을 만들 필요는 없겠죠. 동시에, 메모리의 가격이 낮아지고, 모던 프로그래밍 언어에서는, 어젯듯, 메모리를 관리해주는 많은 옵티마이제이션이 들어가서 상대적으로 덜 중시될 수 있죠. 동시에, 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있다고 해요. 따라서 알고리즘을 평가할 때는, 아무래도, 공간 복잡도보다는 시간 복잡도를 주요하게 볼 수 있죠.
그렇다면, 시간 및 공간 복잡도의 경우 평가 방법이 3가지로 있다고 해요.
최상 : 오메가 표기법 (Big-Ω Notation)
평균 : 세타 표기법 (Big-θ Notation)
최악 : 빅오 표기법 (Big-O Notation)
최상을 놓고 평가하기에는, 항상 그렇지 않기 때문에, 다소 무리가 있고, 그렇다고 평균을 놓고 평가하자니, 최악도 존재하고 해서, 결론적으로 최악의 평가인 빅오 표기법 (Big-O Notation)을 바탕으로 알고리즘의 시간 복잡도를 평가하는 게 일반적이죠.
말이 되죠?
여러분들이, 소프트웨어 엔지니어 혹은 그에 비슷한 직종의 면접을 볼 때, 코딩 시험이라는 것을 보는 것이 일반 적여요. 이 코딩 시험에서 여러 가지 문제들이 있지만, 보편적으로 여러분들이 작성하는 코드들의 복잡도를 계산해서 최적화시키는 부분도 반드시 숙지해놓고 있어야 해요.
하지만, 컴퓨테이셔널 디자이너, 혹은 크리에이티브 코더 들의 코딩 시험에서는 소프트웨어 엔지니어만큼 높은 기준을 요구하지는 않는 것 같아요. 아무래도 무개 중심이 코드 옵티마이제이션도 중요하지만, 크리에이티브한 설루션, 즉 디자인 문제를 풀기 위한 창의적인 알고리즘이 판단기준이 아닐까 해요.
그럼에도 불구하고, 위와 같은 사항을 숙지해서 습관화한다면 더 실력 있는 스페셜리스트가 될 수 있죠!
빅오 표기법 (Big-O Notation)시간 복잡도 Time Complexity
O(1) : 상수(constant) - 보라색
아래 예제처럼 입력되는 자료의 크기에 관계없이 복잡도는 동일하게 유지되죠.
void add(int a, int b) {
return a +b;
}
O(log N) : 로그(Logarithmic) - 파란색
logN : 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타날 수 있어요. 즉, 입력 자료의 수에 따라 실행시간이 logN의 관계를 만족한다면 N이 증가할 때, 선형으로 증가되기보다는, 조금씩 늘어나게 되죠. 그래프와 같은 트리 혹은 이진 탐색같이 전체의 데이터를 쪼개면서 연산할 경우 예가 있을 수 있어요.
O(N) : 선형, Linear - 노란색 부분 - 녹색
입력 자료의 수에 따라 선형적으로 실행 시간이 걸리는 경우죠. 입력이 증가하면 처리 시간 또는 메모리 사용이 비례에서(선형적)으로 증가해요. 일반적인 for loop을 그 예로 들 수 있어요
void sum(List <int> nums) {
int result = 0;
for(int i = 0 ; i < nums.count; ++i) {
result += nums[i];
}
return result;
}
O(N^2) : Square 혹은 Quadratic - 빨간색
반복문이 두 번 있는 케이스 흔히 이중(더블) 루프, double for loop라고 이야기하는 경우예요. 이 유형은 이중 루프 내에서 입력 자료를 처리하는 경우에 나타나요. N값이 큰 값이 되면 실행 시간은 감당하지 못할 정도로 커지죠.
double sumDistances(List<Point3d> pts ) {
int result = 0;
for(int j = 0 ; j < pts.count; ++j) {
for(int i = 0 ; i < pts.count; ++i) {
result += distance(pts[j], pts[i] );
}
}
return result;
}
O(N^3) : Cubic
이 유형은 앞의 유형과 비슷하게 입력 자료를 삼중 루프 내에서 처리하는 경우에 나타나요
for(int k = 0 ; k < dataC; ++k) {
for(int j = 0 ; j < dataB; ++j) {
for(int i = 0 ; i < dataA; ++i) {
// TODO
}
}
}
O(2ⁿ) : Cubic , O(N!) 등등
입력자료의 수가 늘어남에 따라 급격히 실행 시간이 늘어나요. 이 유형은 흔하지는 않지만 가끔씩 알고리즘을 처음 개발할 때 보인다고 해요. 일반적으로, 특정 데이터들을 돌면서 다른 데이터 세트와 매치를 하고 또 다른 계산들을 하고 등등의 구현을 하고. 인풋과 아웃풋이 정확하게 작동하게 되면, 그 후, 리펙토링을 통해 코드를 최적화하는 순으로 개발을 하죠.
공간 복잡도 Space Complexity
간단하게 공간 복잡도의 예도 알아보죠.
O(1) : 상수(constant) - 보라색
메모리에(스택) 각각의 변수가 그 스콥 안에서 선언되기 때문에 n 개수와 상관없이 O(1)로 볼 수 있습니다.
int factorialLoop(int n) {
int i = 0;
int sum = 1;
for(i = 1; i <= n; ++i){
sum *= i;
}
return sum;
}
O(N) : 선형, Linear - 노란색 부분 - 녹색
메모리(스택)에 함수가 재귀적으로 n 개수만큼 호출됨으로 O(n)으로 볼 수 있어요.
int factorialRecursive(int n){
if(n > 1) {
return n * factorialRecursive(n - 1);
} else {
return 1;
}
}
reference: https://en.wikipedia.org/wiki/Time_complexity
revision 01 -2020/3/24
