알고리즘의 이론적 분석에서는 점근적 의미에서 복잡성을 추정하는 것이 일반적입니다. 즉, 임의의 큰 입력에 대한 복잡도 함수를 추정합니다. "알고리즘 분석"이라는 용어 Donald Knuth가 만들었습니다.
알고리즘 분석은 특정 계산 문제를 해결하기 위해 알고리즘에 필요한 리소스에 대한 이론적 추정을 제공하는 계산 복잡도 이론의 중요한 부분입니다. 대부분의 알고리즘은 임의 길이의 입력으로 작동하도록 설계되었습니다. 알고리즘 분석은 그것을 실행하는 데 필요한 시간과 공간 자원의 양을 결정하는 것입니다.
일반적으로 알고리즘의 효율성 또는 실행 시간은 시간 복잡도로 알려진 입력 길이와 단계 수를 관련시키는 함수로 표시됩니다. , 또는 공간 복잡성으로 알려진 메모리의 양 .
이 섹션에서 다룰 내용 -
- 알고리즘 및 복잡성
- 점근적 분석
- 점근적 표기법
- 상각 상각 분석
- 공간 복잡성
- 의사 다항식 유형 알고리즘 및 PATS(의사 다항식 유형 근사화 체계)