알고리즘에서의 점근적 분석

소개글

알고리즘의 분석 방법 중 점근적 분석에 대한 내용입니다.

목차

1.알고리즘 개요
2.알고리즘 분석
3.복잡도 분석
4.점근적 분석

본문내용

1.알고리즘 개요
알고리즘이란? 컴퓨터용어로서 알고리즘은 어떤 문제의 해결을 위해 컴퓨터가 사용 가능한 정확한 방법을 말한다. 알고리즘은 여러 단계의 유한한 집합으로 구성되는데, 여기서 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. 이 때 컴퓨터가 각 연산들을 수행하기 위해서는 다음의 조건을 만족해야 한다. ①명확성: 각 연산들은 명확한 의미를 가져야 한다. ②효율성: 각 연산은 원칙적으로 일정한 시간 내에 사람이 연필로 할 수 있어야 한다. ③입력: 외부 입력자료가 있을 수 있다. ④출력: 하나 이상의 결과가 나온다. ⑤종결성: 유한 번의 연산 후에는 끝나야 한다.

2.알고리즘 분석
주어진 문제를 해결하기 위한 알고리즘을 선택해야 할 경우 알고리즘이 문제를 얼마나 효율적으로 풀 수 있는지 결정 할 수 있어야 한다. 다시 말해, 시간이나 메모리의 효율을 분석할 수 있어야 한다. 메모리 공간이 제약이 가장 큰 고려사항이라면 알고리즘의 공간복잡도(Space Complexity)가 효율성 분석에 측정 대상이 될 수 있지만 특별한 환경이 아니라면 메모리의 공간제약은 문제가 되지 않는다. 따라서 다음 설명에서도 시간복잡도(Time Complexity)를 대상을 설명할 것이다.

참고 자료

없음