일정 시간과 상각 일정 시간은 효과적으로 동등하다고 간주됩니까?

Amortized Constant Time은 거의 항상 Constant Time과 동일하게 간주 될 수 있으며 애플리케이션의 세부 사항과 수행하려는 사용 유형을 알지 못합니다. 이 대기열에서 대부분의 기회는 여러분이 다루게 될 것입니다.

배열 목록에는 기본적으로 가장 큰 크기 / 길이 / 항목 수와 동일한 용량 개념이 있습니다. 지금까지 요구되었습니다. 따라서 처음에는 배열 목록이 계속해서 항목을 추가함에 따라 용량을 늘리기 위해 계속 재 할당되지만, 어느 시점에서는 단위 시간당 추가되는 평균 항목 수가 불가피하게 평균 항목 수와 일치합니다. 단위 시간당 제거됩니다 (그렇지 않으면 결국 메모리가 부족해집니다).이 시점에서 어레이는 자체 재 할당을 중지하고 모든 추가는 O (1)의 일정한 시간에 충족됩니다.

그러나 , 기본적으로 배열 목록에서 임의 제거는 O (1)이 아니라 O (N)입니다. 왜냐하면 배열 목록은 제거 된 항목 이후의 모든 항목을 한 위치 아래로 이동하여 제거 된 항목을 대신하기 때문입니다. . O (1)을 달성하려면 제거 된 항목을 배열 목록의 마지막 항목의 복사본으로 대체하는 기본 동작을 재정의 한 다음 마지막 항목을 제거하여 항목이 이동되지 않도록해야합니다. 하지만 그렇게하면 더 이상 대기열이 더 이상 존재하지 않습니다.

댓글

• 젠장, 삭제에 대한 좋은 점입니다. 저는 ' 그것을 고려하지 않았습니다. 그리고 우리는 ' 요소를 무작위로 제거하므로 ' 기술적으로 의미하지 않습니다. ' 어쨌든 그런 의미에서 더 이상 대기열이 아니십니까?
• 예, 실제로 대기열로 취급하지 않는다는 의미입니다. 하지만 제거 할 항목을 어떻게 찾을 계획인지 모르겠습니다. 그것들을 찾는 메커니즘이 그것들이 추가 된 순서대로 대기열에있을 것으로 기대한다면, 당신은 운이없는 것입니다.항목의 순서가 깨져도 상관 없으면 괜찮습니다.
• RandomQueue가 Queue 인터페이스 및 제공된 remove 메소드의 경우 헤드를 터뜨리는 대신 무작위로 제거하므로 ' 특정 순서에 의존하는 방법은 없습니다. 무작위적인 특성을 감안할 때 사용자는 '이 특정 순서를 유지하기를 기 대해서는 안된다고 생각합니다. 나는 명확하게 내 질문에 과제를 인용했습니다. 감사합니다.
• 예, 제가 제안한대로 항목을 삭제했는지 확인하면 괜찮을 것 같습니다.
• 그렇지 않으면 마지막으로 한 가지 ' 괜찮습니다. 저는 ' 더 많이 생각했지만 ' 같지 않은 것 같습니다 ' " true " O (1) 추가 및 " true " O (1) 무작위 제거; 그것은 ' 2 사이의 상충 관계가 될 것입니다. 제거는 제공하지만 추가는 제공하지 않는 단일 할당 구조 (배열과 같은) 또는 Linked-와 같은 청크 할당 구조가 있습니다. 추가는 제공하지만 제거는 제공하지 않는 목록입니다. 이것이 사실입니까? 다시 한 번 감사드립니다.

이 질문은 상각 된 일정 시간 . 따라서 인용 된 질문과 관련하여 아니오, 사실상 동일하지 않습니다 *. 그러나 실제 응용 프로그램에 있습니까?

상각 된 상수의 일반적인 문제는 때때로 누적 된 부채를 지불해야한다는 것입니다. 따라서 삽입은 일반적으로 일정하지만 때로는 새 블록이 할당 될 때 모든 것을 다시 삽입해야하는 오버 헤드를 겪어야합니다.

일정 시간과 상각 된 일정 시간의 차이가 응용 프로그램과 관련이 있는지 여부에 따라 다릅니다. 가끔 매우 느린 속도가 허용됩니다. 매우 많은 도메인의 경우 일반적으로 괜찮습니다. 특히 컨테이너의 유효 최대 크기 (예 : 캐시, 임시 버퍼, 작업 컨테이너)가있는 경우 실행 중에 비용을 한 번만 효과적으로 지불 할 수 있습니다.

응답이 중요한 애플리케이션에서 이러한 시간은 허용되지 않을 수 있습니다. 단시간 처리 보증을 충족해야하는 경우 때때로이를 초과하는 알고리즘에 의존 할 수 없습니다. 이전에 그런 프로젝트에 참여한 적이 있지만 매우 드뭅니다.

또한이 비용이 실제로 얼마나 높은지에 따라 다릅니다. 벡터는 재 할당 비용이 상대적으로 낮기 때문에 잘 수행되는 경향이 있습니다. 그러나 해시 맵으로 이동하면 재 할당이 훨씬 더 높아질 수 있습니다. 다시 말씀 드리지만, 대부분의 응용 프로그램에서는 괜찮을 것입니다. 특히 컨테이너의 항목에 대한 상한선이있는 수명이 긴 서버에 적합합니다.

*하지만 여기에는 약간의 문제가 있습니다. 범용 컨테이너를 만들기 위해서는 삽입을위한 일정한 시간이어야합니다. 다음 두 가지 중 하나가 유지되어야합니다.

• 컨테이너는 고정 된 최대 크기를 가져야합니다. 또는
• 개별 요소의 메모리 할당이 일정한 시간이라고 가정 할 수 있습니다. .

댓글

• " 간 서버 "는 여기서 사용하기에 이상한 표현 인 것 같습니다. " 라이브 서버 "를 의미합니까?

처리량 또는 지연 시간을 최적화하는지 여부에 따라 다릅니다.

• 지연- 민감한 시스템에는 일관된 성능이 필요합니다. 이러한 시나리오의 경우 시스템의 최악의 동작을 강조해야합니다. 예를 들어 소프트 실시간 시스템은 일관된 프레임 속도를 달성하려는 게임 또는 특정 빡빡한 시간 내에 응답을 보내야하는 웹 서버 : CPU주기를 낭비하는 것이 늦는 것보다 낫습니다.
• 처리량에 최적화 된 시스템은 신경 쓰지 않습니다. 장기적으로 최대 양의 데이터를 처리 할 수있는 한 가끔 중단됩니다. 여기서 우리는 주로 상각 된 성과에 관심이 있습니다. 이는 일반적으로 숫자 처리 또는 기타 일괄 처리 작업의 경우입니다.

하나의 시스템에는 다르게 분류되어야하는 다른 구성 요소가있을 수 있습니다. 예 : 최신 텍스트 프로세서에는 지연 시간에 민감한 UI 스레드가 있지만 맞춤법 검사 또는 PDF 내보내기와 같은 다른 작업을 위해 처리량이 최적화 된 스레드가 있습니다.

또한 알고리즘 복잡성은 종종 우리가 생각하는 것만 큼 중요하지 않습니다. 생각 : 문제가 특정 수에 국한되면 실제 및 측정 된 성능 특성이 “매우 큰 n “의 행동보다 더 중요합니다.

댓글

• 안타깝게도 배경 지식이 거의 없습니다.질문은 다음으로 끝납니다. " RandomQueue의 add (x) 및 remove () 작업은 작업 당 일정한 시간으로 실행되어야합니다 ".
• @Carcigenicate 시스템이 지연 시간에 민감하다는 사실을 알지 못하는 경우 데이터 구조를 선택하기 위해 상각 된 복잡성을 사용하는 것이 절대적으로 충분해야합니다.
• 이것이 그럴 것이라고 생각합니다. 프로그래밍 연습이나 테스트. 그리고 확실히 쉬운 것은 아닙니다. 거의 문제가되지 않는다는 것은 절대적으로 사실입니다.

상각 된 일정 시간을 요구하는 경우 알고리즘을 사용하면 때로는 시간이 오래 걸릴 수 있습니다. 예를 들어 C ++에서 std :: vector를 사용하는 경우 이러한 벡터는 10 개 개체에 대한 공간을 할당했을 수 있으며 11 번째 개체를 할당하면 20 개 개체에 대한 공간이 할당되고 10 개 개체가 복사되고 11 번째 개체가 추가됩니다. 상당한 시간이 걸립니다. 그러나 백만 개의 개체를 추가하면 999,980 개의 빠른 작업과 20 개의 느린 작업이있을 수 있으며 평균 시간은 빠릅니다.

“일정한 시간”알고리즘을 요청하는 경우 알고리즘은 모든 단일 작업에 대해 항상 빠릅니다. 이는 각 단일 작업이 항상 빠르다는 보장이 필요한 실시간 시스템에 중요합니다. “일정한 시간”은 종종 필요하지 않지만 “상각 된 일정 시간”과 동일하지 않습니다 .