연결된 목록과 배열을 사용하여 스택을 구현하는 동안 배가되고 증분되는 전략은 무엇입니까?

Question

amortized와 average complexity의 차이점은 무엇입니까? 또한 연결된 목록 및 배열을 사용하여 스택을 구현하는 동안 배가되고 증분되는 전략은 무엇입니까?

Answer 1

일반적으로 평균 사례 복잡성 및 상환 된 복잡성은 다른 개념을 나타냅니다. 평균 - 케이스 복잡성은 대개 평균화 된 알고리즘 또는 데이터 구조의 런타임을 설명 할 때 사용됩니다. 예를 들어 무작위로 추출한 퀵 정렬의 평균 사례 런타임 (피벗이 임의로 선택되는 경우) 또는 skiplist의 평균 사례 런타임에 대해 이야기 할 수 있습니다.

반면에 상각 된 복잡성은 일반적으로 수행되는 작업의 총 수로 나눈 일련의 작업에 의해 수행 된 전체 작업의 비율을 나타냅니다. 예를 들어 더 많은 공간이 필요할 때마다 크기를 두 배로하는 동적 배열에서 각 개별 추가 작업은 O (n) 작업을 통해 배열 복사 및 요소 전송을 수행 할 수 있습니다. 그러나 이렇게하면 공간이 사용 가능하게 보장되기 때문에 시간 n (1)에 다음 n 개의 작업이 완료됩니다. 결과적으로, n 개의 추가는 총 O (n) 시간이 걸리므로 각 연산의 상각 된 비용은 O (1)입니다. 이것은 총 작업 수 (O (n))와 작업 수 (n)의 비율입니다.

두 개념이 비슷해 보일 수도 있지만 근본적으로 다른 개념을 나타냅니다. 평균 복잡성은 기본 런타임 확률 분포가있는 경우 평균 작업량을 나타냅니다. 상환 된 복잡성이란 특정 작업이 "비싸지 만" "저렴한"작업으로 비용을 지불 할 수 있다는 사실을 기반으로 일련의 작업이 수행하는 평균 작업량을 말합니다. 이런 이유로 일부 데이터 구조 (예 : 재 해싱이 포함 된 연결 해시 테이블)의 평균 작업 시간은 O (1) 분의 평균 처리 시간이 걸리므로 데이터 구조의 n 작업 시퀀스는 모두 O (n) 시간이 소요됩니다 .

두 번째 질문에 대해 배증 전략은 O (1)이 푸시 운영에 대한 상환 된 복잡성을 보장하고 점진적 성장 전략은 그렇지 않습니다. 직관적으로, 더 많은 공간이 필요할 때 배열의 크기를 두 배로 늘리면 n 요소를 크기 2n의 배열에 복사 한 후 공간을 사용할 수 있기 때문에 다음 n 푸시가 "저렴"합니다. 결과적으로 모든 일련의 n 작업은 O (n) 시간이 걸리고 모든 작업에는 O (1) 시간이 상각됩니다. 좀 더 까다로운 수학을 사용하면 에 의한 자릿수가 1보다 큰 임의의 팩터가 O (1) 상각 시간으로 이어질 것이라는 것을 보여줄 수 있습니다.

증분 증가분은이를 보장하지 않습니다. 이 방법으로 생각하십시오. 배열에 k 요소를 추가하고 크기가 10000k 인 배열로 성장하면 다음 k 작업을 빠르게 수행하기 위해 10000k 작업을 수행합니다. 이러한 k 작업을 "저렴하게"수행 한 후에는 어레이를 다시 성장시키기 위해 10001k 작업을 수행해야합니다. 이것은 일련의 n 푸시에 대해 Θ (n)이 작동한다는 것을 보여줄 수 있습니다. 이것이 권장되지 않는 이유입니다.

마지막으로 배열 대 링크 목록에 대해 질문했습니다. 연결된 목록을 사용할 때 효율적으로 (O (1)에서) 새 연결된 목록 셀을 할당하고 체인을 연결할 수 있기 때문에 배가 지거나 증가하는 것에 대해 걱정할 필요가 없습니다. 상수 요인이 더 높지만 상각 된 효율적인 구조보다는 최악의 경우 효율적인 구조입니다.

희망이 도움이됩니다.