목차
#1 알고리즘
알고리즘은 주어진 문제를 해결하는 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술해 놓은 명세서이다.
알고리즘 표현 방법의 종류
- 자연어를 이용한 서술적 표현
알고리즘을 사람이 쓰는 자연어(언어)로 표현하는 방법이다.
자연어는 서술적일 뿐만 아니라 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어렵다. 따라서 누구라도 쉽게 이해하고 쓸 수 있어야 하는 알고리즘을 표현하는데 한계가 있다. - 순서도를 이용한 도식화
알고리즘을 순서도(Flow Chart)를 작성하는 규칙에 따라 도식화하는 방법이다.
순서도를 이용하면 명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는 데에 한계가 있다. - 프로그래밍 언어를 이용한 구체화
알고리즘을 프로그래밍 언어를 사용하여 표현하는 방법이다. 이 방법을 사용하면 알고리즘 자체가 구체화되므로 추가로 구체화 작업을 할 필요가 없다. 하지만... 특정한 프로그래밍 언어로 작성하기 때문에 해당 언어를 모르면 이해하기 힘들다. - 가상코드를 이용한 추상화
알고리즘을 프로그래밍 언어로 표현했을 때 생기는 단점을 보완한 방법이다. 특정 프로그래밍 언어는 아니지만 프로그래밍 언어의 형태를 갖춘 가상(수도) 코드(Pseudo-code)를 사용하여 알고리즘을 표현한다.
C 스타일 가상(의사, 슈도 코드)
void function fizzbuzz
For (i = 1; i<=100; i++) {
set print_number to true;
If i is divisible by 3
print "Fizz";
set print_number to false;
If i is divisible by 5
print "Buzz";
set print_number to false;
If print_number, print i;
print a newline;
}# 알고리즘 성능 분석 기준
알고리즘 성능을 분석하는 판단 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있다.
정확성 : 올바른 자료가 입력되었을 때 유한한 시간 내에 올바른 결과를 출력할 수 있느냐를 말한다.
- 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었느냐를 말한다.
- 수행량 : 기본적으로 포함되는 일반 연산을 제외하고 알고리즘의 특성을 나타내는 중요 연산을 모두 분석.
- 메모리 사용량 : 사용하는 명령어, 변수, 입출력 자료와 정보를 저장하기 위해 사용하는 메모리의 사용량을 분석.
- 최적성 : 알고리즘을 적용할 시스템의 사용 환경과 중요 요구사항이 다르기에 '가장 좋은' 알고리즘이란 조건에
맞는 '최적의 알고리즘'이다.
# 알고리즘 성능 분석 방법
- 공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘을 프로그램으로 실행하여 완료하는 데까지 필요한 총 저장 공간을 의미한다.
필요한 고정 공간과 가변 공간을 합하여 구하는데 고정 공간은 프로그램 크기나 입출력 횟수와는 상관없이 고정적으로 필요한 저장 공간으로 프로그램 저장 공간과 변수 및 상수를 저장하는 공간이며, 가변 공간은 실행 과정에서 사용하는 자료와 변수를 저장하는 공간과 함수를 실행하는 데 관련 있는 정보를 저장하는 공간이다. - 시간 복잡도(Time Complexity)
시간 복장도는 알고리즘을 프로그램으로 실행하여 완료하는 데까지 소요되는 시간이다.
프로그램의 컴파일 시간과 실행 시간을 더해 구하는데 컴파일 시간은 프로그램 특성과 큰 관련이 없으므로 고정된 같은 시간으로 가정하는데 일단 컴파일이 되면 프로그램을 수정하지 않는 한 추가로 컴파일 작업을 하지 않으므로 시간 복잡도에서는 컴파일 시간을 의미 있는 시간으로 취급하지 않는다. 실행 시간은 같은 프로그램이라도 실행되는 컴퓨터의 성능에 따라 달라질 수 있기 때문에 실제 실행 시간을 측정하기보다는 명령문의 실행 빈도수를 계산하여 추정한다.
시간 복장도는 각 알고리즘을 서로 비교하기 위한 것이므로 정확한 실행 시간을 측정하기보다는 실행 빈도수를 구하여 사용한다.
지정문, 조건문, 반복문 안에 있는 제어문과 return 문은 시간 차이가 거의 없으므로 하나의 단위 시간을 갖는 기본 명령문으로 취급하여 실행 빈도수를 구하며 이 과정에서 입력 크기 n에 대한 실행 빈도 함수를 구할 수가 있다.
fibonacci(n)
if( n < 0 ) then
stop;
if ( n <= 1) then
return n;
// 위 조건문의 경우 n < 0, n = 0, n = 1 인 경우로 for문이 수행되지 않아 실행 빈도수와는 큰 위미가 없다.
// 반면 n > 1인 경우 즉, 피포나치 수열을 사용하는 일반적인 경우에는
f1 <- 0;
f2 <- 1;
// for문이 n에 따라 반복하여 수행된다.
for(i <- 2; i <= n; i <- i + 1) do {
fn <- f1 + f2;
f1 <- f2;
f2 <- fn;
}
// 중괄호나 end문은 실행 명령문이 아니므로 실행 시간을 0으로 하며
// for문은 하나의 실행 단위로 계싼한다.
// 총 실행 빈도수를 계싼하면, 1+0+1+0+1+1+n+(n-1)+(n-1)+(n-1)+0+1+0 = 4n + 2이다.
return fn;
end여기에서 4n + 2는 매개변수 n에 대한 실행 빈도 함수가 된다.
즉 실행 시간은 n에 따라 정해지는데 n = 10이면 4 * 10 + 2 = 42가 되고, n이 1000이면 4 * 1000 +2 = 4002가 된다.
| 행 번호 | n < 0 | n = 0 | n < 1 |
| 01 | 1 | 1 | |
| 02 | 1 | 0 | 0 |
| 03 | 0 | 1 | 1 |
| 04 | 0 | 1 | 1 |
| 05 ~ 13 | 0 | 0 | 0 |
| 행 번호 | n > 1 | 행 번호 | n > 1 |
| 01 | 1 | 08 | n - 1 |
| 02 | 0 | 09 | n - 1 |
| 03 | 1 | 10 | n - 1 |
| 04 | 0 | 11 | 0 |
| 05 | 1 | 12 | 1 |
| 06 | 1 | 13 | 0 |
| 07 | n | ||
# 알고리즘 성능 분석 표기법
- 빅-오 표기법(Big-Oh Notatio)
빅오 표기법은 O(f(n))과 같이 표기하며, "Big Og of f(n)"으로 읽는다. 실행 빈도 함수에서 구한 시간 복잡도가 n²이라면 O(n²)으로 표기한다. 빅오 표기법에 대한 수학정 정의는
함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ n ₀인 모든 n에 대해 f(n) ≤ c · |g(n)|를 만족하는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.
빅오 표기법은 함수의 상한을 나타내기 위한 표기법이다. 다시 말해 최악의 경우에도 g(n)의 수행 시간 안에는 알고리즘 수행이 완료된다는 것을 보장한다. - 빅-오메가 표기법(Big-Omega Notation)
'알고리즘' 카테고리의 다른 글
| [알고리즘] 순자 자료구조와 선형 리스트(자료구조5) (2) | 2023.09.16 |
|---|---|
| [알고리즘] 재귀호출(자료구조4) (0) | 2023.09.16 |
| [알고리즘] 구조체(자료구조3) + 데이터베이스 테이블 (0) | 2023.09.15 |
| [알고리즘] 포인터(자료구조2) (2) | 2023.09.14 |
| [알고리즘] 배열(자료구조1) (0) | 2023.09.11 |