상각분석

컴퓨터 과학에서, 상각 분석은 주어진 알고리즘의 복잡성, 또는 실행하는 데 필요한 자원, 특히 시간이나 메모리를 분석하는 방법입니다.상각된 분석의 동기는 최악의 경우 실행 시간을 보는 것이 너무 비관적일 수 있기 때문입니다.대신, 상각 분석은 해당 ^[1]^{: 306}시퀀스에 걸쳐 일련의 운영 실행 시간을 평균화합니다.결론: "변형 분석은 최악의 경우 및 평균 사례 분석과 같은 다른 기술을 보완하는 유용한 도구입니다.“^[2]^{: 14}

알고리즘의 특정 연산에 대해, 특정 상황(예: 입력 매개 변수화 또는 데이터 구조 내용)은 자원의 상당한 비용을 의미할 수 있는 반면, 다른 상황은 비용이 많이 들지 않을 수 있다.상각분석은 전체 영업순서에 걸쳐 원가가 많이 드는 영업과 덜 비싼 영업 모두를 함께 고려한다.여기에는 다양한 유형의 입력, 입력 길이 및 ^[2]그 성능에 영향을 미치는 기타 요인에 대한 고려가 포함될 수 있습니다.

역사

상각분석은 애그리게이트 분석이라고 불리는 방법에서 처음 등장했으며, 현재는 상각분석이 적용되고 있다.이 기법은 Robert Tarjan에 의해 1985년 논문 '상각된 계산 복잡도'^[1]에서 처음 공식적으로 도입되었으며, 이는 일반적으로 사용되는 확률론적 방법보다 더 유용한 형태의 분석의 필요성을 다루었다.상각은 초기에 매우 특정한 유형의 알고리즘, 특히 이진수 트리와 결합 연산을 포함하는 알고리즘에 사용되었습니다.그러나 현재는 어디에나 존재하며 다른 많은 알고리즘도 분석할 때 사용됩니다.^[2]

방법

상각분석을 위해서는 가능한 일련의 연산이 필요합니다.이는 작업 간에 지속되는 상태를 가진 데이터 구조의 경우 가장 일반적입니다.기본적인 생각은 최악의 경우 상태가 바뀌어 최악의 경우 장기간 다시 발생할 수 없으므로 비용이 "증가"될 수 있다는 것입니다.

상각분석을 수행하는 방법에는 일반적으로 집계법, 회계법 및 잠재적 방법의 세 가지가 있습니다.이 모든 것은 정답을 제시합니다.어떤 것을 사용할지는 특정 상황에서 가장 ^[3]편리한지에 따라 결정됩니다.

집계 분석은 일련의 n개 연산의 총비용에 대한 상한 T(n)를 결정하고 상각된 비용을 T(n)/^[3]n으로 계산한다.
회계법은 각 영업에 실제 원가와 다를 수 있는 상각후원가를 할당하는 집계분석의 한 형태이다.초기 운영은 실제 비용보다 상각 비용이 높으며, 이는 실제 비용보다 상각 비용이 낮은 이후 운영을 위해 비용을 지불하는 절약된 "크레딧"을 축적합니다.신용은 0에서 시작되므로 일련의 영업에 대한 실제 원가는 상각후원가에서 누적신용액을 뺀 값과 같다.신용은 음이 아니어야 하므로 상각후원가는 실제원가의 상한선이 된다.일반적으로 많은 단기 운영은 이러한 신용을 조금씩 축적하지만, 드문 장기 운영은 신용을 대폭 ^[3]감소시킵니다.
잠재적 방법은 저장된 신용을 데이터 구조 상태의 함수(잠재적)로 계산하는 회계 방법의 한 형태이다.상각된 비용은 당장의 비용과 ^[3]잠재력의 변화를 더한 값입니다.

예

다이내믹 어레이

동적 배열의 푸시 작업에 대한 상각 분석

다음과 같은 요소가 추가됨에 따라 크기가 커지는 동적 어레이를 고려하십시오.ArrayListJava 또는std::vectorC++로 표시됩니다.크기 4의 동적 배열로 시작하면 4개의 요소를 푸시할 수 있으며, 각 작업은 일정한 시간이 걸립니다.그러나 5번째 요소를 해당 어레이에 푸시하려면 어레이가 현재 크기의 두 배(8)의 새 어레이를 만들고 오래된 요소를 새 어레이에 복사한 후 새 요소를 추가해야 하기 때문에 시간이 더 오래 걸립니다.다음 세 번의 푸시 작업에서도 마찬가지로 일정한 시간이 소요되며, 이후 추가 작업을 수행하려면 어레이 크기가 두 배로 느립니다.

일반적으로 크기 n의 배열에 대한 푸시 n + 1의 임의의 횟수를 고려할 경우 푸시 동작은 크기가 두 배로 커지는 동작을 수행하기 위해 $\Theta (n)$ ( n $)\displaystyle \Theta ( n$ )시간이 $\Theta (n)$ 걸리는 마지막 것을 제외하고 일정한 시간이 걸립니다.총 n + 1 연산이 있었으므로 이 평균값을 구하면 요소를 다이내믹 어레이에 푸시하는 데 ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ( ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ) + ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ( ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ) ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ + ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ( ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ) ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ { $display$ style { $tfrac$ { n \ $Theta (1)+$ $\Theta (n)}{n+1}=\$ $Theta$ (1 ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ 상수 시간.^[3]

큐

다음에 나타낸 것은 큐의 루비 실장 FIFO 데이터 구조입니다.

학급 큐   방어하다 초기화하다     @input = []     @출력 = []   끝.    방어하다 큐잉(요소)     @input << > 요소   끝.    방어하다 큐잉을 해제하다     한다면 @출력.비어있나요?       하는 동안에 @input.없어?         @출력 << > @input.팝       끝.     끝.      @출력.팝   끝. 끝.

enqueue 조작은 입력 어레이에 요소를 푸시하기만 하면 됩니다.이 조작은 입력 또는 출력의 길이에 의존하지 않기 때문에 일정한 시간에 실행됩니다.

그러나 큐 제거 작업은 더 복잡합니다.출력 배열에 이미 요소가 포함되어 있는 경우 디큐는 일정한 시간 내에 실행됩니다.그렇지 않은 경우 디큐는 입력 배열에서 출력 배열에 모든 요소를 추가하는 데 O $O(n)$ ( $O(n)$ ) \ $displaystyle$ O ( $n$ ) $O(n)$ } 시간이 $O(n)$ $O(n)$ .n은 입력 배열의 현재 길이입니다.입력에서 n개의 요소를 복사한 후 출력 배열이 다시 비워지기 전에 각각 일정한 시간이 걸리는 n개의 디큐 작업을 수행할 수 있습니다.따라서 일련의 n개의 디큐 연산을 $O(n)$ O $O(n)$ ( $O(n)$ ){ $displaystyle$ O ( $n$ ) $O(n)$ 만으로 $O(n)$ 실행할 수 있습니다.이는 각 디큐 연산의 상각시간이 O ( $O(1)$ $){$ $displaystyle O$ (1 $O(1)$ ^[4] $O(1)$ 을 의미합니다.

또는 입력 배열에서 출력 배열로 복사하는 비용을 해당 항목의 초기 엔큐 작업에 청구할 수 있습니다.이 과금 방식에서는 enqueue에 대한 상각 시간이 2배로 증가하지만 디큐에 대한 상각 시간은 O $O(1)$ ( $)(\display style O$ (1 $O(1)$ 로 단축됩니다.

일반적인 용도

일반적으로 "변형 알고리즘"은 상각된 분석이 잘 수행됨을 보여주는 알고리즘입니다.
온라인 알고리즘은 일반적으로 상각된 분석을 사용합니다.

레퍼런스

^ ^a ^b Tarjan, Robert Endre (April 1985). "Amortized Computational Complexity" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.
^ ^a ^b ^c Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), archived from the original (PDF) on 20 October 2013, retrieved 3 May 2011
^ ^a ^b ^c ^d ^e Kozen, Dexter (Spring 2011). "CS 3110 Lecture 20: Amortized Analysis". Cornell University. Retrieved 14 March 2015.
^ Grossman, Dan. "CSE332: Data Abstractions" (PDF). cs.washington.edu. Retrieved 14 March 2015.

문학.

"Lecture 7: Amortized Analysis" (PDF). Carnegie Mellon University. Retrieved 14 March 2015.
Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. pp. 20, 141.

[tarjan-1] Tarjan, Robert Endre (April 1985). "Amortized Computational Complexity" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.

[fiebrink-2] Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), archived from the original (PDF) on 20 October 2013, retrieved 3 May 2011

[Lecture_20-3] Kozen, Dexter (Spring 2011). "CS 3110 Lecture 20: Amortized Analysis". Cornell University. Retrieved 14 March 2015.

[Grossman-4] Grossman, Dan. "CSE332: Data Abstractions" (PDF). cs.washington.edu. Retrieved 14 March 2015.

[1]

[2]

[3]

[4]

Search

상각분석

네임스페이스

더

목차

역사

방법

예

다이내믹 어레이

큐

일반적인 용도

레퍼런스

문학.