알고리즘의 상각 분석이란 무엇입니까?

알고리즘의 상각 분석이란 무엇입니까?

---

점근 분석과 어떻게 다릅니 까? 언제 사용하고 왜 사용합니까?

다음과 같이 잘 쓰여진 것 같은 기사를 읽었습니다.

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

그러나 나는 여전히 이러한 개념을 완전히 이해하지 못했습니다.

그래서 누구든지 나를 위해 단순화 할 수 있습니까?

---

상각 분석은 한 번의 호출에 대해 최악의 경우 호출 수를 순진하게 곱하지 않습니다.

예를 들어, 필요할 때 크기가 두 배가되는 동적 배열의 경우 일반 점근 분석은 항목을 추가하는 데 O (n) 비용이 든다는 결론을 내릴 수 있습니다. 모든 요소를 ​​새 배열에 확장하고 복사해야 할 수 있기 때문입니다. 상각 후 분석은 성장을 위해 이전 성장 이후 성장을 유발하지 않고 n / 2 개의 항목을 추가해야한다는 점을 고려하므로 항목을 추가하는 데 실제로는 O (1) 만 필요합니다 (O (n)의 비용은 n / 2 개 조치로 상각 됨 ).

상각 분석은 "평균 성과"와 동일하지 않습니다. 상각 분석은 많은 작업을 수행 할 경우 성과가 무엇을 할 것인지에 대한 확실한 보증 을 제공합니다 .

---

"무엇"에 대한 답은 많지만 "왜"에 대한 답은 없습니다.

다른 모든 사람들이 말했듯이 점근 분석은 주어진 작업의 성능이 어떻게 대규모 데이터 세트로 확장되는지에 관한 것입니다. 상각 분석은 대규모 데이터 세트에 대한 모든 작업의 ​​평균 성능이 어떻게 확장되는지에 대한 것입니다. 상각 분석은 점근보다 더 나쁜 경계를 제공하지 않으며 때로는 훨씬 더 나은 경계를 제공합니다.

더 긴 작업의 총 실행 시간에 관심이 있다면 더 나은 상각 분석 범위가 아마도 관심이있는 것입니다. 그렇기 때문에 스크립팅 언어 (예 :)는 비용이 많이 드는 작업 임에도 불구하고 어떤 요인으로 배열과 해시 테이블을 늘릴 수 있습니다. (성장은 O(n)수술 이 될 수 있지만 상각은 O(1)드물게하기 때문입니다.)

실시간 프로그래밍을 수행하는 경우 (개별 작업은 예측 가능한 시간 내에 완료되어야 함) 상각 된 분석의 더 나은 범위는 중요하지 않습니다. 평균적으로 작업이 빠른지, 너무 멀리 자르기 전에 띠톱을 조정하기 위해 제 시간에 완료하지 못한 경우에는 중요하지 않습니다.

귀하의 경우에 중요한 것은 프로그래밍 문제가 정확히 무엇인지에 달려 있습니다.

---

점근 분석

이 용어는 알고리즘이 작동하는 데이터 ( 입력 )가 평신도의 용어로 "크게 만들면 결론을 변경하지 않을만큼 충분히 크다" 는 가정하에 알고리즘 성능 분석을 나타냅니다 . 입력의 정확한 크기를 지정할 필요가 없지만, 데이터 자체가 설정 (우리는 단지이 상한 필요) 가 지정되어야합니다.

지금까지 분석 방법 에 대해서만 이야기했습니다 . 우리 가 분석 하는 양 (시간 복잡성? 공간 복잡성?)을 정확히 지정 하지 않았고, 우리가 관심 있는 메트릭 (최악의 경우? 최상의 경우? 평균?) 도 지정하지 않았습니다 .

실제로 점근 분석이라는 용어는 일반적으로 알고리즘의 상한 시간 복잡도 , 즉 big-Oh 표기법으로 표시되는 총 실행 시간으로 측정 된 최악의 성능을 나타냅니다 (예 : 정렬 알고리즘은 O(nlogn)).

상각 분석

이 용어는 최악의 시나리오 를 대상으로하는 특정 작업 시퀀스를 기반으로하는 알고리즘 성능 분석을 나타냅니다. 즉, 상각 분석은 메트릭이 최악의 성능이라는 것을 의미합니다 (아직 측정중인 수량을 말하지는 않지만 ). 이 분석을 수행하려면 입력 크기 를 지정해야 하지만 형식에 대한 가정을 할 필요는 없습니다.

평신도의 관점에서 상각 분석은 입력에 대해 임의의 크기를 선택한 다음 알고리즘을 "실행"하는 것입니다. 입력에 따라 결정을 내려야 할 때마다 최악의 경로가 선택됩니다 ¹. 알고리즘이 완료 될 때까지 실행 된 후 계산 된 복잡성을 입력 크기로 나누어 최종 결과를 생성합니다.

¹ 참고 : 정확히 말하면 이론적으로 가능한 최악의 경로 입니다 . 용량이 소진 될 때마다 크기가 동적으로 두 배가되는 벡터가있는 경우, "최악의 경우"는 삽입이 시퀀스로 처리되기 때문에 삽입 할 때마다 두 배가 필요하다고 가정하는 것은 아닙니다 . 우리는 입력이 알려지지 않은 상태에서도 가능한 한 많은 "더 나쁜"경우를 수학적으로 제거하기 위해 알려진 상태 를 사용할 수 있습니다.

가장 중요한 차이점

점근 분석과 상각 분석의 중요한 차이점은 전자는 입력 자체에 의존하고 후자는 알고리즘이 실행할 작업 순서에 의존한다는 것입니다.

따라서:

• 점근 분석을 통해 N 에 접근하는 크기의 최고 / 최악 / 평균 케이스 입력이 주어 졌을 때 알고리즘의 복잡성이 일부 함수 F (N)에 의해 제한 된다는 것을 주장 할 수 있습니다. 여기서 N은 변수입니다.
• 상각 분석을 통해 알려지지 않은 특성의 입력이 주어졌지만 알려진 크기 N이 함수 F (N)의 값보다 나쁘지 않을 때 알고리즘의 복잡성을 주장 할 수 있습니다. 여기서 N은 알려진 값입니다.

---

이에 대한 답은 책-알고리즘 소개 : 상각 된 분석 장의 첫 번째 문장에서 간결하게 정의됩니다.

에서 상각 분석 , 시간 데이터 구조 연산의 시퀀스 동작이 수행되는 모든 평균화 수행해야.

우리는 점근 적 분석을 통해 프로그램 성장의 복잡성을 나타냅니다.이 분석은 프로그램의 성장을 기능으로 제한하고 최악, 최고 또는 평균 사례를 정의합니다.

그러나 이것은 프로그램의 복잡성이 최고점에 도달하는 경우가 하나 뿐이지 만 일반적으로 프로그램이 많은 계산을 필요로하지 않는 경우에는 오해의 소지가 있습니다.

따라서 단일 작업이 비싸더라도 일련의 작업에 대한 비용을 평균화하는 것이 더 합리적입니다. 이것은 상각 분석입니다!

상각 분석은 복잡성을 계산하는 데 사용되는 점근 기법의 대안입니다. 두 개 이상의 알고리즘을 비교하고 결정하기 위해 실용성 측면에서보다 진정한 복잡성을 계산하는 데 도움이됩니다.

---

알고리즘의 상각 분석을 이해하기 위해 지금까지 찾은 최고의 참고 자료는 Introduction to Algorithms , 3 판, 17 장 : "Amortized Analysis"에 있습니다. 모든 것이 있으며 Stack Overflow 게시물에서 찾을 수있는 것보다 훨씬 더 잘 설명되어 있습니다. 괜찮은 대학의 도서관에서 책을 찾을 수 있습니다.

---

정기적 인 점근 분석은 개별 작업의 성능을 문제 크기의 함수로 점근 적으로 살펴 봅니다. O () 표기법은 점근 분석을 나타냅니다.

상각 분석 (점근 분석이기도 함)은 공유 데이터 구조 에서 여러 작업 의 총 성능을 조사합니다 .

차이점은 상각 분석은 일반적으로 M 작업에 필요한 총 계산이 개별 작업에 대한 최악의 경우 M 배보다 더 나은 성능 보장을 제공한다는 것을 증명한다는 것입니다.

예를 들어, 크기 N 의 스플레이 트리 에서 개별 작업 은 최대 O (N) 시간이 걸릴 수 있습니다. 그러나 크기가 N 인 트리에서 M 작업 시퀀스는 O (M (1 + log N) + N log N) 시간으로 제한되며, 이는 작업 당 대략 O (log N)입니다. 그러나 상각 된 분석은 "평균 사례"분석보다 훨씬 더 엄격 합니다. 가능한 모든 작업 시퀀스가 ​​점근 적 최악의 경우를 충족 한다는 것을 증명합니다 .

---

상각 분석은 루틴의 여러 실행에 대한 총 비용과 그에서 얻을 수있는 이점을 다룹니다. 예를 들어, 단일 일치 항목에 대해 정렬되지 않은 n 개의 항목 배열을 검색하면 최대 n 개의 비교가 필요할 수 있으므로 복잡성이 o (n)입니다. 그러나 동일한 배열이 m 개의 항목을 검색 할 것이라는 것을 알고 있다면 전체 작업을 반복하면 복잡성 O (m * n)이됩니다. 그러나 배열을 미리 정렬하면 비용은 O (n log (n))이고 연속 검색은 정렬 된 배열에 대해 O (log (n)) 만 사용합니다. 따라서이 접근법을 사용하는 m 개 요소에 대한 총 상각 비용은 O (n * log (n) + m * log (n))입니다. m> = n이면 정렬하지 않은 경우 O (n ^ 2)와 비교하여 사전 정렬을 통해 O (n log (n))과 같습니다. 따라서 상각 된 비용이 더 저렴합니다.

간단히 말해, 초기에 약간의 추가 비용을 지출하면 나중에 훨씬 절약 할 수 있습니다.

참고URL : https://stackoverflow.com/questions/11102585/what-is-amortized-analysis-of-algorithms