[알고리즘] 알고리즘 분석(1) - 설명

알고리즘이란?? - 주어진 문제를 유한한 시간 내에 해결하는 단계적 절차이다

데이터구조란?? - 데이터를 조직하고 접근하는 체계적 방식이다

우리가 좋은 프로그램을 만들기 위해서는 첫째로 소요되는 "실행시간"을 줄이고, 둘째로 "기억장소 사용량"을 최소화해야 한다

실행시간은 대체로 입력의 크기와 함께 증가한다

입력의크기란 프로그램이 처리해야 하는 어떤 큰 수의 자릿수라던가, 처리해야 하는 데이터원소들의 개수 등을 말한다

실행시간에는 최선실행시간, 평균실행시간, 최악실행시간이 있다

최선실행시간 - 제일 운 좋은 경우의 성능

평균실행시간 - 알고리즘을 평균적인 입력으로 실행한 결과

최악실행시간 - 어떤 알고리즘이 입력에대한 출력을 얻기 위해 가장 오랜시간이 걸리는 경우(분석이 비교적 용이)

실행시간을 구하는 방법에는 실험적인방법과 이론적인방법이 있다

실험적인방법 - 프로그램을 작성 -> 시스템 콜을 사용하여 실제 실행시간을 정확히 측정 -> 도표작성 후 데이터를 수집

이론적인방법 - 실행시간을 의사코드로 표현하여 분석(실험적인방법의 단점을 극복 - 입력데이터가 크면 입력하기 어려움, 하드웨어와 소프트웨어환경차이, 실행을 위한 알고리즘을 완전한 프로그램 구현하기 어려움)

의사코드란 알고리즘을 설명하기 위한 고급언어를 말한다(고급언어란 인간에게 읽히기 위해 쓰이는 것)

-----예시-----            A배열(n개의 정수배열)의 최대값을 반환하는 알고리즘 의사코드

Alg arrayMax(A, n)

input array A of n integers                   

output maximum element of A             

1. currentMax <- A[0]  

2. for i <- 1 to n-1

if (A[i] > currentMax)

currentMax <- A[i]

3. return currentMax

전형적인 함수들의 증가율

상수(c) < 로그(log n) < 로그제곱(log^2 n) < 선형(n) < 로그선형(nlog n) < 2차(n^2) < 3차(n^3) < 지수(2^n)

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사