알고리즘: Difference between revisions
From CS Wiki
No edit summary |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 3: | Line 3: | ||
== 알고리즘의 조건 == | == 알고리즘의 조건 == | ||
=== 알고리즘의 특정 == | === 알고리즘의 특정 === | ||
* 입출력: 0개 이상의 입력을 받으며 1개 이상의 출력을 생성한다. | * 입출력: 0개 이상의 입력을 받으며 1개 이상의 출력을 생성한다. | ||
* 유한성(종결성): 한정된 수행 후 한정된(유한한) 시간 내에 종결되어야 한다. | * 유한성(종결성): 한정된 수행 후 한정된(유한한) 시간 내에 종결되어야 한다. | ||
| Line 10: | Line 10: | ||
* 효율성: 모든 과정은 명백하게 실행 가능한 수준이어야 한다. | * 효율성: 모든 과정은 명백하게 실행 가능한 수준이어야 한다. | ||
== 알고리즘의 선택 기준 == | === 알고리즘의 선택 기준 === | ||
* 정확성 | * 정확성 | ||
* 효율성 | * 효율성 | ||
| Line 25: | Line 25: | ||
;적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단 | ;적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단 | ||
=== 시간 복잡도(Time Complexity) === | === [[시간 복잡도|시간 복잡도(Time Complexity)]] === | ||
* 최악의 경우를 분석 | * 최악의 경우를 분석 | ||
* 최적의 경우를 분석 | * 최적의 경우를 분석 | ||
* 모든 경우를 분석 | * 모든 경우를 분석 | ||
* 평균치 분석 | * 평균치 분석 | ||
* [[점근적 표기법|점근적 표기법(Asymptotic notation)]] | |||
** 최상의 경우 : [[오메가 표기법|오메가 표기법 (Big-Ω Notation)]] | |||
** 평균의 경우 : [[세타 표기법|세타 표기법 (Big-θ Notation)]] | |||
** 최악의 경우 : [[빅오 표기법|빅오 표기법 (Big-O Notation)]] | |||
=== 공간 복잡도(Space Complexity) === | === 공간 복잡도(Space Complexity) === | ||
Latest revision as of 18:43, 25 September 2020
- 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정
알고리즘의 조건[edit | edit source]
알고리즘의 특정[edit | edit source]
- 입출력: 0개 이상의 입력을 받으며 1개 이상의 출력을 생성한다.
- 유한성(종결성): 한정된 수행 후 한정된(유한한) 시간 내에 종결되어야 한다.
- 명확성: 수행 과정은 명확하고 모호하지 않아야 한다. 언어 변경이 수월해야 한다.
- 유효성: 모든 명령들은 오류가 없이 실행 가능해야 한다.
- 효율성: 모든 과정은 명백하게 실행 가능한 수준이어야 한다.
알고리즘의 선택 기준[edit | edit source]
- 정확성
- 효율성
- 적합성: 목표시스템의 SW와 HW에 호환되고, 적합하게 적용될 수 있어야 한다.
알고리즘 생성 절차[edit | edit source]
- 알고리즘 설계
- 포현
- 정확성 검증
- 효율성 분석
알고리즘 평가[edit | edit source]
정확도(Accuracy)[edit | edit source]
- 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단
시간 복잡도(Time Complexity)[edit | edit source]
- 최악의 경우를 분석
- 최적의 경우를 분석
- 모든 경우를 분석
- 평균치 분석
- 점근적 표기법(Asymptotic notation)
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
