자료구조는 메모리의 효율성 뿐만 아니라 실행 시간의 효율성도 따지게 됩니다.
알고리즘 & 자료구조 평가
컴퓨터에서 알고리즘과 자료구조의 평가는 시간과 공간 두 자원을 얼마나 소모하는지가 효율성의 관건이 됩니다.
평균적인 상황에서와 최악의 상황에서의 자원 소모량의 기준이 됩니다.
프로그램의 규모는 점점 방대해져가고 있습니다. 데이터의 양이 적어 무시할 수 있는 정도라면 상관없겠지만 데이터의 양이 늘어날수록 알고리즘 간의 효율성 차이는 더욱 커질 수 밖에 없습니다.
하지만 알고리즘의 절대적인 실행 시간으로 비교할 경우 객관성이 떨어질 수 밖에 없습니다. 누군가는 슈퍼 컴퓨터를 사용해서 실행하고 누군가는 부팅만 겨우 되는 노트북으로 실행할 때 측정 결과로 비교하는 것은 의미가 없어집니다.
따라서 시간 복잡도는 알고리즘의 진행 과정 중 연산이 몇 번 실행되는지를 숫자로 표기해 나타냅니다. 그리고 시간 복잡도는 주로 빅-오 표기법을 이용해 표기합니다.
시간 복잡도 : 알고리즘의 시간적 효율성
공간 복잡도 : 알고리즘의 공간적 효율성
일반적으로 시간을 위해 공간이 희생되는 경우가 많다.
Big-O 표기법
Big-O 표기법은 알고리즘의 복잡도를 나타내는 점근표기법입니다.
알고리즘의 대략적인 효율을 판단할 수 있는 수단입니다.
점근 표기법(asymptotic notation)
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법빅-오 표기법의 경우 프로그램에서 소요되는 시간 중 최악의 경우를 고려합니다.
"이 정도 시간까지 걸릴 수 있다." 를 나타내는데 이는 최선이나 평균의 경우 평소 소요되는 시간보다 오래 걸릴 때 문제점을 파악하는 데 많은 시간이 걸리기 때문입니다.
빅오(Big-O) : 최악의 경우를 고려
빅세타(Big-Θ) : 둘의 중간값(평균)을 고려
빅오메가(Big-Ω) : 최선의 경우를 고려따라서 다른 표기법보다 Big-O 표기법을 자주 사용합니다
Big-O 표기법을 나타내는 법은 가장 높은 차수의 계수를 제거하고 나머지 항을 모두 제거해서 나타냅니다.
- 상수 항 제거
O(2N) -> O(N) - 영향력 없는 항 제거
O(N^2 + 2N + 1) -> O(N^2)
Big-O 표기법의 종류
O(1)
일정한 복잡도라고도 하며 입력값의 크기와 상관없이 바로 출력값을 얻을 수 있습니다.
// 양의 정수 n을 n번 더하는 알고리즘
int Case1(int n)
{
int sum = 0;
sum = n * n;
return sum;
}
// input : 1 => 1
// input : 10 => 1
// input : 100 => 1
// input : 1000 => 1O(1) 에서는 입력값이 어떻든 연산은 단 한 번 수행됩니다.
O(N)
// 양의 정수 n을 n번 더하는 알고리즘
int Case2(int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += n;
}
return sum;
}
// input : 1 => 1
// input : 10 => 10
// input : 100 => 100
// input : 1000 => 1000위 케이스는 입력값에 따라 연산의 횟수가 달라지기 때문에 O(N)을 가집니다.
O(N^2)
// 양의 정수 n을 n번 더하는 알고리즘
int Case3(int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
sum++; // sum += 1;
}
}
return sum;
}
// input : 1 => 1
// input : 10 => 100
// input : 100 => 10,000
// input : 1000 => 1,000,000위 케이스는 입력값에 따라 n * n 번의 연산이 필요한 것을 볼 수 있습니다.
이 때문에 O(N^2)의 시간 복잡도를 가지게 됩니다.
세 가지 케이스 모두 양의 정수 n을 n번 더하는 알고리즘이지만 구현하는 방법에 따라 시간 효율성이 다른 것을 볼 수 있습니다. 늘 효율적인 알고리즘 구현 방법을 생각하는 것이 뛰어난 개발자가 되기 위한 방법 중 하나일 것입니다.
O(log N)
O(log N)은 로그 복잡도라고도 부릅니다. O(1) 보다 빠른 시간 복잡도를 가지고 있습니다. 이후 나올 내용인 BST(Binary Search Tree)가 O(log N)의 시간 복잡도를 가지고 있습니다.
예를 들어 업&다운 게임을 생각해보면 최대 숫자가 100일 경우 중간 숫자를 말할 때 마다 경우의 수가 절반으로 줄어들게 됩니다. 이러면 계속 정답을 맞추지 못 하여도 7번이면 정답을 맞출 수 있게 됩니다.
BST(이진 탐색 트리) 또한 이러한 로직을 가지고 있으며, 이를 O(log N)의 시간 복잡도를 가진 알고리즘(탐색 기법)이라고 합니다.
void Case4(int n)
{
int i = 1;
while(i < n)
{
i *= 2;
}
}
i는 1, 2, 4, 8 ... 으로 올라가므로 연산은 log nO(2^N)
최악의 시간 복잡도입니다.
종이를 42번 접으면 지구에서 달까지 닿을 수 있다고 합니다.만약 구현한 알고리즘이 이러한 시간 복잡도를 가지고 있다면 다른 방식을 생각해보는 것이 좋겠습니다.
이러한 시간 복잡도를 가진 알고리즘의 예로 피보나치 수열이 있습니다.
피보나치 수열은 첫 항이 1, 둘째 항이 1이며 그 뒤의 항은 앞의 두 항의 합이 되는 수열입니다. ( 1, 1, 2, 3, 5 ... )
피보나치 수열을 구하는 대표적 알고리즘은 재귀함수를 이용하는 것입니다.
재귀함수는 함수 내에서 자기 자신을 한 번 더 호출하는 함수입니다.
예시를 보겠습니다.
void Fibonacci(int n)
{
if(n <= 1)
{
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2); // 함수 내에서 자기 자신을 호출
}시험 삼아 아무 입력값을 넣고 입력해보시기 바랍니다.
틀린 내용이나 추가적인 내용에 관한 의견 주시면 감사하겠습니다. (_ _)
