[알고리즘] 알고리즘 기초 (수행시간 분석 / 표기법)

알고리즘이란 ?

주어진 문제를 효율적으로 풀기위한 방법을 단계별로 기술해놓은 것.

 

알고리즘 설명 4단계

① Problem definition (문제 정의)
② Algorithm description (알고리즘 설명)
③ Correctness proof (정확성 증명)
④ Performance Analysis (성능분석)
           - Running Time (수행시간)
           - Space Consumption (사용공간)

 

수행시간 분석

수행연산의 횟수를 비교하는 방식
입력 크기 n에 대한 함수로 표현 : T(n)

 

성능 분석의 비교대상

산술연산 (Arithmetic Calculation)   :   Add, Multiply, Exponent, Modular
데이터 입출력 (Data Movement)    :   Copy, Move, Save, Load
제어연산 (Access Control)             :  If, While, Register

 

* Exponent : 지수 연산, n제곱

* Modular : 나머지 연산

 

점근적 표기법

① 빅오       : 알고리즘을 실행하는 최대 실행시간을 표기
② 오메가    : 알고리즘을 실행하는 최소 실행시간을 표기
③ 세타       : 알고리즘을 실행하는데 걸리는 최대, 최소 실행시간을 모두 표기