회계방법(컴퓨터공학)

전산학 알고리즘 분석 분야에서 회계 방식은 회계에 근거한 상각 분석 방식이다.회계법은 종종 총액 분석이나 잠재적 방법보다 영업 상각후원가에 대한 더 직관적인 회계처리를 제공한다.그러나 이것이 그러한 분석이 즉시 명백해지리라는 것을 보장하지는 않는다. 종종 회계방법에 대한 올바른 매개변수를 선택하는 것은 다른 두 가지 방법처럼 문제에 대한 많은 지식이 필요하며 복잡성의 한계를 증명하려고 시도한다.

회계방법은 O(1)를 제 시간에 묶는 것을 증명하는 데 가장 적합하다.여기서 설명한 방법은 그러한 한계를 증명하기 위한 것이다.

방법

알고리즘에서 사용될 기본 운영 세트를 선택하고 그 비용을 임의로 1로 설정한다.이러한 운영의 비용이 현실에서 다를 수 있다는 사실은 원칙적으로 어려움이 없음을 나타낸다.중요한 것은 각각의 초등 운영비가 일정하다는 점이다.

각 집계 작업에는 "지급"이 할당된다.이 지불은 이 특정 운영을 완료하는 데 필요한 기본적인 운영 비용을 충당하기 위한 것으로, 일부 지불은 남겨두고 나중에 사용할 풀에 넣어두어야 한다.

상각분석을 필요로 하는 문제점의 어려움은 일반적으로 일부 영업에서는 일정한 원가보다 더 큰 비용이 소요된다는 것이다.이것은 그 자체로 최악의 수술 비용을 감당하기에 충분한 지속적인 지불은 없다는 것을 의미한다.그러나 적절한 지급을 선택하면 이는 더 이상 어려운 문제가 아니다. 비싼 운영은 그들의 비용을 충당할 충분한 지급이 풀에 있을 때에만 발생할 것이다.

예

몇 가지 예는 회계 방법의 사용을 설명하는 데 도움이 될 것이다.

테이블 확장

얼마나 많은 공간이 필요한지 알기 전에 테이블을 만들어야 하는 경우가 많다.한 가지 가능한 전략은 테이블이 가득 차 있을 때 그 크기를 두 배로 하는 것이다.여기서 우리는 그러한 표의 삽입 작업에 대한 상각후원가가 O(1)임을 보여주기 위해 회계 방법을 사용할 것이다.

절차를 자세히 보기 전에 몇 가지 정의가 필요하다.내버려두다T식탁이 되다,E삽입할 요소, 안에 있는 요소의 개수(T)T, 및 할당된 크기(T)T. operation create_table(n)이 존재한다고 가정하며, 크기가 비어있는 테이블을 생성한다.n, 현재 무료라고 가정하고 요소를 삽입하는 초급_insert(T,E)E테이블로T1의 비용으로 이미 공간이 할당되어 있다.

다음 유사 코드는 테이블 삽입 절차를 보여준다.

함수 table_insert(T, E) = size(T) U := create_table(2 × size(T) 각 F in T season_insert(U, F) T := U season_insert(T, E)

상각해석 없이, n 삽입 연산에 대해 우리가 보여줄 수 있는 최선의 바운드는 O(n)이다. 이는 num(T) 기본 삽입을 수행하는 라인 4의 루프 때문이다.

회계법을 이용한 분석은 테이블 삽입마다 3개씩 지급을 할당한다.지금은 그 이유가 명확하지 않지만 분석 과정에서 분명해질 것이다.

처음에 테이블이 크기(T) = m로 비어 있다고 가정하십시오.따라서 첫 번째 m 삽입물은 재할당이 필요하지 않으며 비용 1만 가지고 있다(기본 삽입의 경우).따라서 num(T) = m일 때 풀은 (3 - 1)×m = 2m이다.

요소 m + 1을 삽입하려면 테이블의 재분배가 필요하다.3호선에 새 테이블을 만드는 것은 무료다.4호선의 루프는 m의 원가를 위해 m 기본 삽입을 필요로 한다.마지막 줄에 삽입하는 것을 포함하여, 이 작업에 대한 총 비용은 m + 1이다. 따라서 이 작업 후에 풀은 2m + 3 - (m + 1) = m + 2가 된다.

다음으로 표에 m - 1 원소를 추가한다.이 때 풀은 m + 2 + 2×(m - 1) = 3m이다.추가 요소(즉, 요소 2m + 1)를 삽입하면 비용이 2m + 1이고 대금이 3인 것으로 볼 수 있다.이 작업 후 풀은 3m + 3 - (2m + 1) = m + 2가 된다.이는 요소 m + 1을 삽입한 후와 동일한 양이라는 점에 유의하십시오.사실, 우리는 이것이 어느 정도의 재분배에도 해당될 것이라는 것을 보여줄 수 있다.

이제 왜 삽입에 대한 지불이 3. 원소의 첫 번째 삽입에 대한 지불, 1은 다음 테이블이 확장될 때 요소 이동에 대한 지불, 1은 다음 테이블이 확장될 때 오래된 요소 이동에 대한 지불을 지불하는지 명확히 할 수 있다.직관적으로, 이것은 테이블이 확장되는 횟수에 관계 없이 요소의 기여도가 결코 "고갈되지 않는다"는 이유를 설명하는데, 테이블은 항상 두 배로 늘어나기 때문에, 가장 오래된 반쪽을 이동하는 데 드는 비용은 항상 최신의 반쪽이 부담한다.

우리는 처음에 테이블을 만드는 것이 무료라고 가정했다.실제로 n사이즈의 테이블을 만드는 것은 O(n)만큼 비쌀 수도 있다.n사이즈의 테이블을 만드는 비용은 n이라고 하자.이 새로운 비용이 어려움을 초래하는가?그렇지 않다. 상각된 O(1) 한계를 표시하기 위해 동일한 방법을 사용하는 것으로 나타났다.우리가 해야 할 일은 결제를 변경하는 것이다.

새 테이블을 만들면 m 항목이 있는 오래된 테이블이 있다.새 테이블은 2m 크기로 만들어질 것이다.현재 표에 있는 항목들이 새 표를 만드는 데 지불할 만큼 풀에 추가되는 한, 우리는 괜찮을 것이다.

새 테이블의 결제에 도움이 되는 첫 $번째{\displaystyle \frac{}{}}$ m ${\displaystyle \frac{2}{}}$ ${\$개의 항목을$$ 예상할 수 없다.그 항목들은 이미 현재 표에 대한 비용을 지불했다.그런 다음 마지막 $m{\displaystyle \frac{}{}}$ ${\displaystyle \frac{2}{}}$ ${\$개 항목에$$ 의존하여 비용을 ${\displaystyle \mathrm{2m}}$ ${\displaystyle 2m}$ 지불해야 한다$.$${\displaystyle \frac{즉}{}}$, 각 항목의 ${\displaystyle \mathrm{지급액}}$에 ${\displaystyle \frac{}{}}$ /${\displaystyle \frac{2\mathrm{}}{}}$= 4 ${\displaystyle {\frac {2m}{m/2}}=4}$을(를) 추가해야 하며, 총 지급액은 3 + 4 = 7이다.

참조

• 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 2001. ISBN0-262-03293-7.제17.2절: 회계방법, 페이지 410-412.