- 알고리즘에서 '시간복잡도'와 '공간복잡도'란 무엇인가? 그리고 이것들은 왜 중요한가?
⚡️ 알고리즘 성능 평가
어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까요?
알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다고 합니다.
그중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 합니다.
시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
1. ⚡️시간복잡도(Time Complexity)
시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스입니다.
1-1. 빅-오 표기법
-
시간 복잡도에는 빅-오 표기법이라는 개념이 나옵니다.
-
예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생합니다.
-
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부릅니다.
1-2. 시간 복잡도 그래프
※ 여기서 n이란 입력되는 데이터를 의미합니다.
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)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.
그래프와 위 설명을 참고하여, 시간 복잡도에 따른 성능을 비교하면 아래와 같습니다.
faster O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!) slower
slower로 갈수록(즉, 오른쪽 방향으로 갈수록) 효율성이 떨어집니다.
1-3. 예
1-3-1. 시간 복잡도 O(1)
int[] test = new int[2];일반적인 프로그램이 1라인이 실행되는 것은 1이라고 표현합니다.
1-3-2. 시간 복잡도 O(n)
int[] test = new int[n];
for(int i=0;i<test.length;i++){
test[i] = i;
}반복문이 N번만큼 반복하므로 위의 복잡도는 O(n)입니다.
1-3-3. O(3n)-> 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이 빠르겠지요 그러니 상수에 대해서 무조건 신경 쓰지 말라는 것은 아닙니다.
1-3-4.O(n^2)
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²)입니다. 시간복잡도 계산에서는 정확한 값을 산출하는 것이 아니라 근사치를 계산하기 때문입니다.
위의 O(n²)은 j가 i부터 시작하면서 조금씩 줄여나가도 한번에 완전히 절반이 되는것이 아니기 때문에 logN이 아닌 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²)입니다.
1-4. 시간복잡도 줄이는 법
위에서 예상하셨을 수도 있을 텐데 시간 복잡도에서 반복문이 가장 시간 소모에 가장 큰 영향을 미칩니다. 그렇기에 시간 복잡도를 줄이는 방법은 반복문의 숫자를 줄이는 것입니다.
두번째로는 조건문을 줄이는 것 입니다. 너무 많은 조건문이 있다면 거기서 한번씩 멈추기 때문에 시간이 n * 조건문 숫자 만큼 됩니다.
세번째로는 자료구조를 적절하게 이용하는 방법입니다. 가장 효율적인 자료구조들을 적절히 사용한다면 시간 복잡도를 최대한 줄일 수 있습니다.
네번째로는 알고리즘을 적절하게 이용하는 것입니다. 대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등이 있을 텐데요. 효율적인 알고리즘을 공부해뒀다가 적절할 때 사용한다면 큰 효과를 볼 수 있습니다.
빅오 표기법 예제
O(1) : 스택의 Push, Pop
O(log n) : 이진트리
O(n) : for 문
O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
O(2ⁿ) : 피보나치 수열
2. ⚡️공간복잡도(Space Complexity)
-
작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다.
-
하지만 예전에 비해 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도는 떨어졌다고 합니다.
시간 복잡도의 경우 알고리즘을 잘못 구성하면 결괏값이 나오지 않거나 너무 느린 속도로 나와서 최근에는 시간 복잡도를 더 우선시하여 프로그래밍을 작성한답니다!
2-1. 정리하자면
- 시간과 공간은 반비례적 경향이 있음
- 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
- 알고리즘은 시간 복잡도가 중심
2-2. 예
2-2-1. O(1)
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)입니다.
2-2-2. O(n)
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)이라고 하는것입니다.
2-3.공간복잡도를 줄이는 방법
공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.
프로그램에 필요한 공간은 크게 두가지로 나눌 수 있습니다.
고정 공간
가변 공간
시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적입니다.
또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다.
특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에
만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로 짜는게 더 효율적이라고 볼 수 있습니다.
3. 중요성
알고리즘의 시간복잡도와 공간복잡도는 알고리즘이 얼마나 효율적으로 동작하는지를 측정하는 두 가지 중요한 개념입니다. 이들은 알고리즘의 성능을 분석하고, 다양한 알고리즘 중에서 가장 효율적인 알고리즘을 선택하는 데 도움을 줍니다. 다음은 시간복잡도와 공간복잡도를 사용하는 이유를 설명합니다:
3-1. 성능 비교
시간복잡도와 공간복잡도는 다양한 알고리즘들을 비교하여 어떤 알고리즘이 더 효율적인지를 판단하는 데 도움을 줍니다. 시간복잡도는 알고리즘의 실행 시간을 나타내며, 공간복잡도는 알고리즘이 사용하는 메모리 공간의 양을 나타냅니다. 두 복잡도를 분석하여, 실행 시간이나 메모리 사용량이 작은 알고리즘을 선택할 수 있습니다.
-> 그래서 최적화 및 자원관리를 효율적으로 할 수 있기 때문에 중요성이 높습니다.
3-2. 최적화
시간복잡도와 공간복잡도를 통해 알고리즘의 성능을 최적화할 수 있습니다. 복잡도를 분석하여 알고리즘이 어떤 입력에 대해 느릴 수 있는지, 메모리 부족 현상이 발생할 수 있는지 등을 파악하여 알고리즘을 개선하고 최적화할 수 있습니다.
3-3자원 관리
시간복잡도와 공간복잡도는 시스템 자원을 효율적으로 관리하는 데 도움을 줍니다. 시간복잡도가 높은 알고리즘은 실행 시간이 길어져 시스템의 처리량을 저하시킬 수 있고, 공간복잡도가 높은 알고리즘은 메모리 부족으로 인한 성능 저하가 발생할 수 있습니다. 따라서, 시간복잡도와 공간복잡도를 고려하여 시스템 자원을 효율적으로 관리하고 최적화할 수 있습니다.
참고
