알고리즘과 표기법

알고리즘이란 ?

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

 

알고리즘 설명 4단계

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

 

재귀와 반복

[재귀]

실행 도중 자기 자신을 호출하는 함수로 특정 조건을 만족하면 멈춘다.

재귀 함수가 자신을 호출하는 횟수가 최대 재귀 깊이를 초과하면 스택 오버플로 에러가 발생한다.

 

[반복]

특정 조건이 만족될 때까지 실행이 되풀이 되는 함수.

종료 조건이나, 반복 횟수를 지정하지 않으면 스택 오퍼플로 에러가 발생한다.

 

* 최대 재귀 깊이 : maximum recursion depth

* 스택 오버플로 에러 :  stack over follow error 

 

알고리즘의 세가지 유형

[분할정복 알고리즘]

큰 문제를 여러 개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결방법을 얻는 알고리즘.

 

[탐욕 알고리즘]

실행되는 순간마다 최선의 결정을 하는 알고리즘으로 결과값이 정답인지는 알 수 없다. (결과값 근사치)

*n개의 도시를 모두 방문하는 최단 경로를 탐욕 알고리즘으로 찾으려면 현재 위치에서 가장 가까운 도시를 방문하면서 나아가는 것이다. 그러나 이 결과가 실제 최단경로인지는 알 수 없다.

 

[동적 프로그래밍]

과거에 내린 결정을 저장한 후 나중에 사용하는 알고리즘.

과거에 내린 결정이 앞으로의 결과에 영향을 미치는 알고리즘.

알고리즘 분석

[시간복잡도]

알고리즘이 문제를 해결할 때 걸리는 시간

알고리즘의 성능을 분석할 때 가장 일반적으로 사용되는 방법

 

[공간복잡도]

알고리즘이 문제를 해결할 때 점유하는 컴퓨터의 메모리 공간

자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에만 사용하는 분석 방법

수행시간 분석

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

 

성능 분석의 비교대상

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

 

* Exponent : 지수 연산, n제곱

* Modular : 나머지 연산

 

점근적 표기법

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

 

빅오 표기법

• O(1) : 상수형 알고리즘. 데이터 입력량과 무관하게 실행시간이 일정하다.
• O(n) : 선형 알고리즘. 데이터 입력량에 비례하여 실행 시간이 늘어난다.
• O(logN) : 로그형 알고리즘. 데이터 입력량이 늘어날수록 실행시간이 줄어든다. 
• O(NlogN) : 선형-로그형 알고리즘, 데이터 입력량이 N배 늘어나면 실행시간이 N배 조금 넘게 늘어난다.
• O(N²) : 2차 알고리즘. 데이터 입력량의 제곱만큼 수행시간이 늘어난다.
• O(2ⁿ) : 지수형 알고리즘. 데이터 입력량에 따라 수행시간이 2배로 늘어난다.
• O(n!) : 계승(팩토리얼)형 알고리즘이며, 데이터 입력이 추가될 때마다 실행시간이 n배로 늘어난다.

 

출처

• 코드없는 알고리즘과 데이터 구조, 암스트롱 수베로, 동양북스
• 컴퓨터 알고리즘 기초 1강 컴퓨터 알고리즘 개요(1), T아카데미
• 컴퓨터 알고리즘 기초 1강 컴퓨터 알고리즘 개요(2), T아카데미