DAA-분석 방법론
알고리즘의 리소스 소비를 측정하기 위해이 장에서 설명하는 다양한 전략이 사용됩니다.
점근 분석
함수의 점근 적 동작 f(n) 의 성장을 나타냅니다 f(n) 같이 n 커집니다.
우리는 일반적으로 작은 값을 무시합니다. n, 우리는 일반적으로 큰 입력에서 프로그램이 얼마나 느려질 지 추정하는 데 관심이 있기 때문입니다.
좋은 경험 법칙은 점근 성장률이 느릴수록 알고리즘이 더 좋다는 것입니다. 항상 사실은 아니지만.
예를 들어, 선형 알고리즘 $ f (n) = d * n + k $는 항상 2 차 알고리즘 인 $ f (n) = cn ^ 2 + q $보다 점근 적으로 낫습니다.
반복 방정식 풀기
반복은 더 작은 입력에 대한 값의 관점에서 함수를 설명하는 방정식 또는 부등식입니다. 재발은 일반적으로 분할 및 정복 패러다임에 사용됩니다.
고려하자 T(n) 크기 문제에 대한 실행 시간 n.
문제 크기가 충분히 작 으면 다음과 같이 말합니다. n < c 어디 c 상수이고, 간단한 솔루션은 일정한 시간이 걸립니다. θ(1). 문제를 나눌 때 크기가 $ \ frac {n} {b} $ 인 여러 하위 문제가 발생하는 경우.
문제를 해결하기 위해 필요한 시간은 a.T(n/b). 분할에 필요한 시간을 고려하면D(n) 하위 문제의 결과를 결합하는 데 필요한 시간은 C(n), 반복 관계는 다음과 같이 나타낼 수 있습니다.
$$ T (n) = \ begin {cases} \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ : \ theta (1) & if \ : n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) & 그렇지 않으면 \ end { 사례} $$
반복 관계는 다음 방법을 사용하여 해결할 수 있습니다.
Substitution Method −이 방법에서 우리는 경계를 추측하고 수학적 귀납법을 사용하여 우리의 가정이 옳다는 것을 증명합니다.
Recursion Tree Method −이 방법에서는 각 노드가 비용을 나타내는 반복 트리가 형성됩니다.
Master’s Theorem − 이것은 반복 관계의 복잡성을 찾는 또 다른 중요한 기술입니다.
상각 된 분석
상각 분석은 일반적으로 일련의 유사한 작업이 수행되는 특정 알고리즘에 사용됩니다.
상각 분석은 일련의 작업 비용을 별도로 제한하는 대신 전체 시퀀스의 실제 비용에 대한 제한을 제공합니다.
상각 분석은 평균 사례 분석과 다릅니다. 확률은 상각 분석에 포함되지 않습니다. 상각 분석은 최악의 경우 각 작업의 평균 성능을 보장합니다.
디자인과 분석이 밀접하게 관련되어 있기 때문에 분석 도구 일뿐만 아니라 디자인에 대한 사고 방식입니다.
집계 방법
집계 방법은 문제에 대한 글로벌 뷰를 제공합니다. 이 방법에서n 작업에 최악의 시간이 소요됨 T(n)전체적으로. 그런 다음 각 작업의 상각 된 비용은T(n)/n. 다른 작업에 다른 시간이 걸릴 수 있지만이 방법에서는 다양한 비용이 무시됩니다.
회계 방법
이 방법에서는 실제 비용에 따라 다른 작업에 다른 요금이 할당됩니다. 작업의 상각 된 비용이 실제 비용을 초과하면 차액이 대변으로 객체에 할당됩니다. 이 크레딧은 상각 된 비용이 실제 비용보다 적은 후속 작업에 대한 지불을 돕습니다.
실제 비용과 상각 된 비용이 ith 작업은 $ c_ {i} $ 및 $ \ hat {c_ {l}} $입니다.
$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} $$
잠재적 인 방법
이 방법은 선불 작업을 크레딧으로 간주하는 대신 선불 작업을 잠재적 에너지로 나타냅니다. 이 에너지는 향후 운영 비용을 지불하기 위해 방출 될 수 있습니다.
우리가 수행하면 n 초기 데이터 구조로 시작하는 작업 D0. 고려해 보겠습니다.ci 실제 비용으로 Di 데이터 구조로 ith조작. 잠재적 함수 Ф는 실수 Ф (Di), 관련 잠재력 Di. 상각 된 비용 $ \ hat {c_ {l}} $는 다음과 같이 정의 할 수 있습니다.
$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i})-\ Phi (D_ {i-1}) $$
따라서 총 상각 비용은
$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limits_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i} )-\ Phi (D_ {i-1})) = \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n})-\ Phi (D_ {0}) $ $
동적 테이블
테이블에 할당 된 공간이 충분하지 않으면 테이블을 더 큰 크기의 테이블에 복사해야합니다. 마찬가지로 테이블에서 많은 수의 멤버가 지워진 경우 더 작은 크기로 테이블을 재 할당하는 것이 좋습니다.
상각 분석을 사용하면 상각 된 삽입 및 삭제 비용이 일정하고 동적 테이블의 사용되지 않은 공간이 전체 공간의 일정한 비율을 초과하지 않음을 보여줄 수 있습니다.
이 튜토리얼의 다음 장에서는 점근 표기법에 대해 간략하게 설명합니다.