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}) $ $

동적 테이블

테이블에 할당 된 공간이 충분하지 않으면 테이블을 더 큰 크기의 테이블에 복사해야합니다. 마찬가지로 테이블에서 많은 수의 멤버가 지워진 경우 더 작은 크기로 테이블을 재 할당하는 것이 좋습니다.

상각 분석을 사용하면 상각 된 삽입 및 삭제 비용이 일정하고 동적 테이블의 사용되지 않은 공간이 전체 공간의 일정한 비율을 초과하지 않음을 보여줄 수 있습니다.

이 튜토리얼의 다음 장에서는 점근 표기법에 대해 간략하게 설명합니다.