자료구조 기초 (2)

알고리즘의 이해

알고리즘 : 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

 

알고리즘의 조건

ƒ 입력input : 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다.

ƒ 출력output : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다.

ƒ 명확성definiteness : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다.

ƒ 유한성finiteness : 알고리즘은 수행 뒤에 반드시 종료되어야 한다.

ƒ 효과성effectiveness : 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다

 

알고리즘의 표현 방법의 종류

ƒ 자연어를 이용한 서술적 표현 방법

ƒ 순서도Flow chart를 이용한 도식화 표현 방법

ƒ 가상코드Pseudo-code를 이용한 추상화 방법

ƒ 프로그래밍 언어를 이용한 구체화 방법

 

알고리즘의 표현방법

1. 가상코드

가상코드, 즉 알고리즘 기술언어ADL, Algorithm Description Language를 사용하여 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 표현

ƒ 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능

ƒ 일반적인 프로그래밍 언어의 형태이므로 원하는 특정 프로그래밍 언어로의 변환 용이

ƒ 기본 요소

• 기호

− 변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블 등을 나타냄

− 문자나 숫자의 조합. 첫 문자는 반드시 영문자 사용

• 자료형

− 정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형 사용

• 연산자

− 산술연산자, 관계연산자, 논리연산자

 

2. 조건문

3. 다단계 조건문

- 중첩 if문

- case문

4. 반복문

-while-do문

-do-while문

5. 함수문

 

알고리즘의 예

 

Example : 알고리즘 Selection Sort

a) 문제 서로 다른 n개의 정렬되지 않은 수가 list에 저장되어 있을 때, 크기가 작은 순서대로 정렬하라.

b) 문제의 설명 다음 리스트 list[5]에서 오름차순으로 정렬하는 문제 list[0] 6 list[1] 5 list[2] 3 list[3] 4 list[4] 2

c) 알고리즘

 for (i = 0 ; i < n; i++)

//Examine list[i] to list[n-1] and suppose that the smallest integer is at list[min];
//Interchange list[i] and list[min];

//구체화
void SelectionSort(int *a, const int n)
{// Sort the n integers a[0] to a[n-1] into nondecreasing order.
	for (int i = 0; i < n; i++)
	{
		int j = i;
		// find smallest integer in a[i] to a[n-1]
		for (int k = i+1; k < n; k++)
			if (a[k] < a[j]) 
				j = k;
		swap (a[i], a[j])

 

알고리즘 성능 분석 기준

ƒ 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등 있음

• 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부

• 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가? 명확할수록 이해하거나 변경하기 쉬움

• 수행량 : 일반적인 연산은 제외, 알고리즘의 특성을 나타내는 중요 연산을 모두 분석

• 메모리 사용량 : 명령어, 변수, 입출력 자료와 정보 저장

• 최적성 : 시스템의 사용 환경과 요구 사항이 다르므로 조건에 맞는 최적의 알고리즘이 가장 중요

 

성능 분석 방법

ƒ 공간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양

• 공간 복잡도 = 고정 공간 + 가변 공간

ƒ 시간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간

• 시간 복잡도 = 컴파일 시간 + 실행 시간

− 컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요

− 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산

• 실행 빈도수의 계산

− 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차이가 거의 없으므로 하나의 단위시간을 갖는 기본 명령문으로 취급

 

 

알고리즘 성능 분석 표기법 (그냥 가볍게 읽었음)

ƒ 빅-오 표기법

• O(f(n))과 같이 표기, “Big Oh of f(n)”으로 읽음

• 수학적 정의

− 함수 f(n)이 주어졌을 때, 모든 n≥ n0에 대하여 |f(n)| ≤ c |g(n)|을 만족하는 상수 c 와 n0이 존재하면, f(n) = O(g(n))이다.

• 함수의 상한을 나타내기 위한 표기법

− 최악의 경우에도 g(n)의 수행 시간 안에는 알고리즘 수행 완료 보장

• 먼저 실행 빈도수를 구하여 실행 시간 함수를 찾고, 이 함수값에 가장 큰 영향을 주는 n에 대한 항을 한 개 선택하여 계수는 생략하고 O의 오른쪽 괄호 안에 표시

• 피보나치 수열(자료에있음)에서 실행 시간 함수는 4n+2이고, 가장 영향이 큰 항은 4n인데 여기에서 계수 4를 생략하여 O(n)으로 표기

 

빅오메가, 빅 세타 표기법도 있음.

시간 복잡도를 정확히 계산할 수 있다면 빅-세타 표기법 사용

시간 복잡도를 정확히 계산할 수 없다면 빅-오 표기법 사용