설명하기에 앞서 우선 알고리즘을 이해해보는 시간을 가지도록 하겠습니다.
알고리즘을 모르고 시간 복잡도와 공간 복잡도만 알고 계시다면 효과가 반감 될 수 도 있기 때문이지요.
0. 알고리즘이란?
목차로 이동
어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정을 의미 하는 것이다.
알고리즘을 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 하고 문제 해결이나 처리 과정에서의 순서를 단계적으로 서술 해야 한다.
왜 이런것을 설명하였는가?
시간복잡도와 공간복잡도는 이러한 알고리즘을 평가하기 위한 지표이기 때문이다.
1. 시간복잡도
목차로 이동
시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다
시간복잡도를 나타내는 점근적 분석법의 표기법으로는 아래와 같으며 주로 최악의 경우인 빅오 표기법 (Big-O Notation) 을 사용하는데 그 이유는 평균의 경우를 사용하면 그 기준을 맞추기 까다롭고 모호할 수 있으며 최악의 경우를 사용하면 “아무리 나빠도 다른 알고리즘 보다는 같거나 좋다.” 라는 비교분석을 따르면 평균에 가까운 성능을 예측하기 쉽기 때문이다.
최상의 경우 : 오메가 표기법 (Big-Omega(Ω) Notation)
평균의 경우 : 세타 표기법 (Theta(θ) Notation)
최악의 경우 : 빅오 표기법 (Big-O Notation)
빅-오 표기법
시간 복잡도에는 여러 개념이 있지만 그중에서 ‘아무리 많이 걸려도 이 시간 안에는 끝날 것‘의 개념이 제일 중요합니다. 예를 들어 동전을 튕겨서 뒷면이 나올 확률을 이야기해본다면 운이 좋으면 한 번에 뒷면이 나올 수도 있고 운이 좋지 않으면 3번 4번만에 뒷면이 나올수도 있습니다. 운이 나쁜 경우 n번만큼 동전을 튕겨야 하는 최악의 경우가 발생하는데
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 부르며 이 방식을 가장 많이 사용합니다.
- 시간 복잡도 그래프
O(1) (Constant)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.
O(log₂ n) (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.
O(n) (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있습니다.
O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적입니다.
O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.
O(2ⁿ) (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.
int[] test = new int[3];
int inTest[2] = 4;일반적인 프로그램이 1라인이 실행되는 것은 1이라고 표현합니다. 위의 시간 복잡도는 O(1)입니다.
int[] test = new int[n];
for(int i=0;i<test.length;i++){
test[i] = i;
}반복문이 N번만큼 반복하므로 위의 복잡도는 O(n)입니다.
int[] test = new int[n];
int[] test2 = new int[n*2];
for(int i=0;i<test.length;i++){
test[i] = i;
}
for(int i=0;i<test2.length;i++){
test2[i] = i;
}N번만큼 반복하는 반복문이 2개가 있습니다. 착각할 수도 있지만 O(n²)이 아닌 O(n)입니다. 시간 복잡도 계산에는 가장 큰 영향을 미치는 알고리즘 하나만 시간복잡도를 계산합니다. O(n) 반복문이 하나가 있으나 3개가 있으나 수십개가 있으나 나타내는것은 O(n)입니다.
하지만 나타내는것만 그렇지 O(3n) 으로 상수가 있습니다. 이상수를 무시해도 좋을 정도는 아닐 수도 있으니 이 상수가 커진다면 고민 하면서 하셔야합니다.
왜냐하면 만약 n이 1억개입니다. 이 앞에 상수가 1000개인것과 10개인것과 2개인 있습니다.
O(1,000N) 과 O(5N)과 O(2N)중 어떤것이 빠르고 좋겠습니까?
1억 *1000과 = 1조
1억 * 5개 = 5억
1억 * 2개 = 2억2N이 빠르겠지요 그러니 상수에 대해서 무조건 신경 쓰지 말라는 것은 아닙니다.
int[][] test2 = new int[n][n];
for(int i=0;i<test.length;i++){
for(int j=i;j<test[0].length;j++{
test[i][j] = i+j;
}
}
위의 경우에는 내부 for문의 변수 j의 값이 i 이므로 엄연히 이중 for문보다 시간이 적게 걸리지만 그래도 시간 복잡도는 O(n²)입니다. 시간복잡도 계산에서는 정확한 값을 산출하는 것이 아니라 근사치를 계산하기 때문입니다.
여기서 j가 i부터 시작하면서 조금씩 줄여나가도 한번에 완전히 절반이 되는것이 아니기 때문에 O(nlogN)이 아닌 O(n²)으로 표시됩니다.
int[][] test2 = new int[n][n];
for(int i=0;i<test.length;i++){
for(int j=i;j<test[0].length;j++{
test[i][j] = i+j;
}
}
int[] test2 = new int[n*2];
for(int i=0;i<test.length;i++){
test[i] = i;
}이중 for문 1개와 for문 1개가 있습니다. 이때는 시간 복잡도에 영향을 더 많이 끼치는 이중 for문 하나만 계산하여 시간복잡도는 O(n²)입니다.
시간복잡도 줄이는 법
위에서 예상하셨을 수도 있을 텐데 시간 복잡도에서 반복문이 가장 시간 소모에 가장 큰 영향을 미칩니다. 그렇기에 시간 복잡도를 줄이는 방법은 반복문의 숫자를 줄이는 것입니다.
두번째로는 조건문을 줄이는 것 입니다. 너무 많은 조건문이 있다면 거기서 한번씩 멈추기 때문에 시간이 n * 조건문 숫자 만큼 됩니다.
세번째로는 자료구조를 적절하게 이용하는 방법입니다. 가장 효율적인 자료구조들을 적절히 사용한다면 시간 복잡도를 최대한 줄일 수 있습니다.
네번째로는 알고리즘을 적절하게 이용하는 것입니다. 대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등이 있을 텐데요. 효율적인 알고리즘을 공부해뒀다가 적절할 때 사용한다면 큰 효과를 볼 수 있습니다.
수많은 개발자가 이 수치를 낮추기위해 엄청난 노력을 한다. '10% 빨라졌다, 20% 자원을 절약한다'와 같은 말은 이 복잡도를 줄이는데서 나온 결과다.
O(n)에서 O(log n)으로 낮추는 극적인 경우는 많이 없다. 그러나 O(3n+2)에서 O(2n)수준 정도 개선이라도 매우 가치있다.
2. 공간복잡도
공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다
최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다. 시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성합니다.
공간복잡도 계산법 (빅-오)
int a = 10;일반적으로 공간이 하나씩 생성되는것을 1이라고 표현합니다. 위의 공간복잡도는 O(1)입니다.
int get_factorial(int n)
{
int i = 0;
int result = 1;
for(i = 1; i <= n; i++)
{
result = result * i;
}
return result;
}반복문이 N번만큼 반복하여도 for문 안에서의 지역변수이므로 위의 공간복잡도는 O(1)입니다. n의 값에 상관없이 함수를 호출하고 i와 result의 변수만 사용됩니다. 다른것은 전혀 영향을 주지 못합니다. 여기서 공간복잡도는 O(1)입니다.
int get_factorial(int n)
{
if(n > 1) return n * factorial(n - 1);
else return 1;
}위처럼 재귀함수일 경우에는 이야기가 달라집니다. 위의 예제를 보시면 함수의 인자값 n에 따라 공간복잡도가 달라집니다. 함수 내부에서 n이 1이하일때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 위의 공간 복잡도는 O(n)입니다.
여기서 이러한 생각을 가지신 분이 계실 수 있습니다. 함수 밖으로 나오면 저것은 사라지니까 O(1)이 아닌가요?
하지만 알고리즘이 한번 실행하여 종료 될때까지가 공간 복잡도 입니다 재귀의 경우 뒤에서 부터 하나씩 변수를 가지고 있기 때문에 n부터 1까지 모두 쌓아 공간 복잡도는 O(n)이라고 하는것입니다.
공간복잡도를 줄이는 방법
공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.
프로그램에 필요한 공간은 크게 두가지로 나눌 수 있습니다.
- 고정 공간
- 가변 공간
시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적입니다.
또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다.
특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에
만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로 짜는게 더 효율적이라고 볼 수 있습니다.
3. 중요한이유
목차로 이동
시간복잡도는 유저의 요청을 빠른 속도로 처리해주기 위해서 알고리즘을 사용하며 공간 복잡도의 경우 컴퓨터의 공간을 계산하여 알고리즘 실행시 공간이 부족하여 멈추지 않게 하기 위해서 계산하여 사용해서
두개다 프로그램의 알고리즘을 만들시 계산하여 사용해야 합니다.
참고자료
