DAA-알고리즘 분석

알고리즘의 이론적 분석에서는 점근 적 의미에서 복잡도를 추정하는 것이 일반적입니다. 즉, 임의로 큰 입력에 대한 복잡도 함수를 추정하는 것입니다. 용어"analysis of algorithms" Donald Knuth가 만들었습니다.

알고리즘 분석은 특정 계산 문제를 해결하는 데 필요한 알고리즘 리소스에 대한 이론적 추정을 제공하는 계산 복잡성 이론의 중요한 부분입니다. 대부분의 알고리즘은 임의 길이의 입력으로 작동하도록 설계되었습니다. 알고리즘 분석은 알고리즘을 실행하는 데 필요한 시간과 공간 자원의 양을 결정하는 것입니다.

일반적으로 알고리즘의 효율성 또는 실행 시간은 입력 길이와 단계 수를 관련시키는 함수로 표시됩니다. time complexity또는 메모리 볼륨 (로 알려진 space complexity.

분석의 필요성

이 장에서는 알고리즘 분석의 필요성과 하나의 계산 문제를 다른 알고리즘으로 해결할 수 있으므로 특정 문제에 대해 더 나은 알고리즘을 선택하는 방법에 대해 설명합니다.

특정 문제에 대한 알고리즘을 고려함으로써 우리는이 알고리즘의 도움으로 유사한 유형의 문제를 해결할 수 있도록 패턴 인식을 개발할 수 있습니다.

이러한 알고리즘의 목적은 동일하지만 알고리즘은 종종 서로 상당히 다릅니다. 예를 들어, 숫자 세트는 다른 알고리즘을 사용하여 정렬 할 수 있습니다. 한 알고리즘에 의해 수행되는 비교 횟수는 동일한 입력에 대해 다른 알고리즘에 따라 다를 수 있습니다. 따라서 이러한 알고리즘의 시간 복잡도는 다를 수 있습니다. 동시에 각 알고리즘에 필요한 메모리 공간을 계산해야합니다.

알고리즘 분석은 필요한 시간 및 크기 (구현 중 저장을위한 메모리 크기) 측면에서 알고리즘의 문제 해결 능력을 분석하는 프로세스입니다. 그러나 알고리즘 분석의 주요 관심사는 필요한 시간 또는 성능입니다. 일반적으로 다음과 같은 유형의 분석을 수행합니다.

• Worst-case − 모든 크기 인스턴스에서 수행되는 최대 단계 수 a.

• Best-case − 모든 크기 인스턴스에서 수행되는 최소 단계 수 a.

• Average case − 모든 크기 인스턴스에서 수행 된 평균 단계 수 a.

• Amortized − 크기 입력에 적용되는 일련의 연산 a 시간이 지남에 따라 평균.

문제를 해결하려면 프로그램이 메모리가 제한되어 있지만 적절한 공간이 사용 가능한 시스템에서 실행되거나 그 반대 일 수 있으므로 시간과 공간의 복잡성을 고려해야합니다. 이 맥락에서 비교하면bubble sort 과 merge sort. 버블 정렬에는 추가 메모리가 필요하지 않지만 병합 정렬에는 추가 공간이 필요합니다. 병합 정렬에 비해 버블 정렬의 시간 복잡도가 높지만 메모리가 매우 제한된 환경에서 프로그램을 실행해야하는 경우 버블 정렬을 적용해야 할 수 있습니다.