알고리즘
알고리즘(영어: algorithm 알고리듬[*], IPA: [ǽlɡərìðm])이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.
목차[숨기기] |
[편집] 알고리즘의 조건
알고리즘은 일반적으로 다음의 조건을 만족해야 한다.
- 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
- 출력 : 적어도 1개 이상의 결과를 내어야 한다.
- 명확성 : 각 명령어들은 명확하고 모호하지 않아야 한다.
- 유한성 : 알고리즘의 명령어들은 유한번의 수행후에 종료되어야 한다. 이것은 수행 시간의 현실적인 유한성을 의미한다.(무한루프에 빠져서는 안된다.)
- 수행가능성 : 모든 명령은 명백하게 실행 가능한 것이어야 한다. 실행 가능하지 않은 알고리즘은 의미가 없다.
[편집] 알고리즘의 연구 분야
- 고안 : 완벽한 자동화를 통한 알고리즘의 개발은 거의 불가능하다. 따라서 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한 알고리듬을 개발하는 데 그 의미가 있다.
- 검증 : 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를 밝히는 절차가 필요하다. 알고리즘 검증은 고안된 알고리듬이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는 데 그 목적이 있다.
- 분석 : 고안된 알고리듬을 실행하기 위해 필요한 실행시간과 필요로 하는 기억장치를 결정하는 것이다.
- 테스트 : 디버깅, 성능분석
[편집] 알고리즘의 분석 기준
- 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
- 작업량 : 전체 알고리듬에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
- 기억 장소 사용량
- 단순성
- 최적성 :그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다
[편집] 평균과 최악의 경우 분석
- O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
- O(log N) : 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
- O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
- O(N log N) : 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.
- O(N2) : 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.
- O(N3) : 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.
- O(2n) : 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.
- O(n!) : 입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법
[편집] 같이 보기
- 알고리즘 (algorism)
[편집] 바깥 고리
- (영어) Algorithms - 오픈 디렉터리 프로젝트
[숨기기]
컴퓨터 과학의 주요 분야 | |
---|---|
수학적 기초 | |
계산 이론 | |
알고리즘 & 자료 구조 | |
프로그래밍 언어 & 컴파일러 | |
병렬 & 분산 시스템 | |
소프트웨어 공학 | |
시스템 아키텍처 | |
통신 & 네트워크 | |
데이터베이스 | |
인공 지능 | |
컴퓨터 그래픽 | 시각화 · 영상 처리 |
인간과 컴퓨터 상호 작용 | 컴퓨터 접근성 · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실 |
계산과학 | 인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치 해석 · 기호계산 |
정보보호 |
'사는 이야기 > 수학사전' 카테고리의 다른 글
이산세계(수가 흩어지기도 하고 모아지기도 하는 세계:수학세계) (0) | 2012.04.27 |
---|---|
‘제노포비아(xenophobia·외국인 혐오증)’ (0) | 2012.04.25 |
유리식 [有理式, rational expression] (0) | 2012.04.19 |
분수함수 [分數函數, fractional function] (0) | 2012.04.19 |
번분수 [繁分數, complex fraction] (0) | 2012.04.19 |