자료구조
프로그램에서 자료들을 정리하여 보관하는 여러 가지 구조를 자료구조라고 한다.
알고리즘
주어진 문제를 처리하는 단계적인 절차를 알고리즘이라고 한다.
추상 자료형(ADT)
자료들과 그 자료들에 대한 연산들을 명시한 것이다.
자료 구조는 다음과 같은 ADT 형태로 구현하면 된다.
- 사용자가 ADT가 제공하는 연산만을 사용할 수 있다.
- 사용자는 ADT가 제공하는 연산들을 사용하는 방법을 알아야 한다.
- 사용자는 ADT 내부의 데이터를 접근, 수정할 수 없다.
- 사용자는 ADT가 어떻게 구현되는지 모르더라도 ADT를 사용할 수 있다.
- 다른 사람이 ADT의 구현을 변경하여도 인터페이스가 변경되지 않으면 사용자는 같은 방식으로 ADT를 사용할 수 있다.
객체지향언어는 클래스 개념을 사용하여 ADT가 구현된다.
알고리즘 성능 분석
1.수행시간 측정
동일한 조건에서 실제로 알고리즘을 구현하고 수행시간을 측정하는 방법은 정확하고 확실한 방법이다.
C언어에서는 2가지 방법으로 수행시간을 측정할 수 있다.
1.clock() 함수
#include <stdio.h>
#include <time.h>
int main()
{
clock_t start = clock();
/*....*/
clock_t stop = clock();
double duration = (double)(stop - start) / CLOCKS_PER_SEC;
printf("%lf", duration);
}clock()함수는 CLOCK_PER_SEC 단위로 시간을 반환한다. 따라서 초단위의 시간을 측정하기 위해서는 (stop - start)값을 CLOCK_PER_SEC로 나눠준다.
2.time(), difftime()
#include <stdio.h>
#include <time.h>
int main()
{
double start = time(NULL);
/*....*/
double stop = time(NULL);
double duration = (double)difftime(stop, start);
printf("%lf", duration);
}time() 함수는 초 단위로 시간으로 반환한다. 따라서 시작과 종료 지점에 time()함수를 호출하고 difftime()을 호출하면 그 차이가 초단위로 반환된다.
이 방법에는 몇가지 문제가 있다.
1.알고리즘을 구현하고 테스트하는 것이 필요하다.
단순한 알고리즘은 쉽게 구현할 수 있지만 복잡한 경우에는 구현해야 되는 것은 큰 부담이 될 수 있다.
2.반드시 똑같은 하드웨어를 사용하여 알고리즘들의 수행시간을 측정해야 한다.
슈퍼컴퓨터에서의 비효율적인 프로그램이 일반 컴퓨터에서의 가장 효율적인 프로그램보다 더 빠른 시간에 수행될 수 있다.
3.소프트웨어 환경도 동일해야한다.
C와 같은 컴파일 언어를 사용한 경우 파이썬과 같이 인터프린트 언어를 사용한 경우보다 빠른 수행을 보인다. 또한 시험되지 않은 입력에 대해 다른 결과를 보일 수 있다.
2. 복잡도 분석
알고리즘을 구현하지 않고 알고리즘의 효율성을 따져보는 기법이 개발되었다. 이는 모든 입력을 고려하고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.
알고리즘 분석에는 2가지 측면을 고려할 수 있다.
- 시간 복잡도
- 공간 복잡도
1.시간 복잡도 함수
알고리즘의 절대적인 수행시간을 나타내는 것이 아닌 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시한다. 여기서 연산에는 덧셈, 곱셈 또는 대입 연산, 비교 연산도 포함된다.
보통 프로그램은 연산의 수행횟수가 정해지지 않고 프로그램에 주어지는 입력의 개수 n에 따라 변하게 된다. 따라서 시간 복잡도 함수는 고정된 숫자가 아닌 n에 대한 함수로 정의된다.
연산의 수를 입력의 개수 n에 대한 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n)이라고 표기한다.
ex) 양의 정수 n을 n번 더하는 문제의 시간 복잡도를 구해라.
3가지 방법이 있을 수 있다.
- n과 n을 곱한다.
- n을 n번 더한다.
- 1을 n*n번 더한다.
위의 알고리즘의 연산 횟수를 표로 만들면 다음과 같다.
| 1번 알고리즘 | 2번 알고리즘 | 3번 알고리즘 | |
| 대입연산 | 1 | n | n * n |
| 덧셈연산 | n | n * n | |
| 곱셈연산 | 1 | ||
| 전체연산수 | 2 | 2n | $2n^2$ |
모든 연산의 수행 시간이 같다고 가정하면 위와 같다. 그러나 곱셉연산이 덧셈연산보다 시간이 더 걸릴 것이다. 따라서 하나의 연산이 t만큼의 시간이 걸린다고 하면 1번은 2t, 2번은 2nt, 3번은 2$n^2t$만큼의 시간이 걸린다.
2.빅오 표기법(최악의 경우)
$T(n) = n^2 + n + 1$
다음과 같은 시간 복잡도 함수가 있고 n이 1000일 때 T(n)의 값은 1,001,001이다.
$n^2$의 값은 전체 값의 99.9%이고 두번째 항인 n의 값은 전체 값의 0.1%을 차지한다.
입력 자료의 개수가 크면 차수가 가장 큰 항이 전체의 값을 주도한다. 따라서 보통 시간복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분하다. 또한 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다.
다음은 많이 쓰이는 빅오 표기법을 순서대로 표시한 것이다.
| Complexity | 1 | 10 | 100 |
| O(1) | 1 | 1 | 1 |
| O($logn$) | 0 | 2 | 5 |
| O(n) | 1 | 10 | 100 |
| O($nlogn$) | 0 | 20 | 461 |
| O($n^2$) | 1 | 100 | 10000 |
| O($n^3$) | 1 | 1000 | 1000000 |
| O($2^n$) | 2 | 1024 | 1267650600228229401496703205376 |
| O(N!) | 1 | 3628800 | 화면에 표현할 수 없음 |
다음은 빅오 표기법에 의한 알고리즘의 수행시간을 비교한 것이다.
$O(1) < O(log n) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)$
3.빅오메가 표기법(최선의 경우)
알고리즘을 실행시켰을 때 최소로 걸릴 수 있는 시간을 말한다.
즉 빅오메가가 낮을수록 최선의 경우 알고리즘이 빠르게 진행된다.
4.빅세타 표기법(평균)
빅오와 빅오메가의 공통부분으로 최소와 최악의 중간인 평균적인 복잡도를 말한다.
현실에서 가장 많이 쓰는 표기법은 빅오 표기법이다. 왜냐하면 알고리즘의 평균적인 시간은 의미가 없는 경우가 많다. 따라서 알고리즘을 구성할 때 최악의 경우인 빅오 표기법을 줄이는 방법으로 알고리즘을 짜는 것이 좋다..
