C++에서 실행 중앙값 계산

1. 실행 중 중앙값
2. C++에서 실행 중앙값 계산

이것은 실행 중앙값을 효율적으로 계산하는 방법에 대한 자습서입니다. 실행 중 중앙값에 대한 자세한 설명부터 시작하여 알고리즘 및 몇 가지 구현 고려 사항이 이어집니다.

실행 중 중앙값

연속 중앙값은 일련의 숫자를 계산하는 효율적인 방법입니다. 중앙값에 관심이 있는 경우 시퀀스의 모든 값을 알 필요는 없지만 대신 얼마나 많은 값이 위 또는 아래에 있는지 추적할 수 있습니다.

짝수의 값이 있는 경우 양쪽 절반의 평균(또는 평균)을 취하여 새로운 중간 값으로 사용합니다.

실행 중앙값은 정렬된 목록의 중간에 있는 관측값으로 시작합니다. 다음 관찰은 이 중간 관찰과 비교됩니다. 더 크거나 작으면 새로운 중간점이 됩니다.

이 프로세스는 정렬된 목록에 더 이상 관찰이 남지 않을 때까지 계속됩니다.

C++에서 실행 중앙값 계산

실행 중앙값은 두 개의 힙을 사용하여 계산됩니다. 현재 중앙값보다 작거나 같은 모든 값은 왼쪽 힙에 있습니다.

현재 중앙값보다 크거나 같은 값은 모두 오른쪽 힙에 있습니다.

실행 중 중앙값은 이 두 힙의 각 숫자를 교환하여 업데이트됩니다. 일정한 수의 스왑을 유지하려면 이 두 힙 중 하나가 비어 있는 시기를 알 수 있는 방법이 필요합니다.

이 두 힙 중 하나가 비어 있으면 현재 중앙값보다 작거나 같은 값이 모두 처리되고 그보다 크거나 같은 값이 모두 처리되었음을 의미합니다. 이 시점에서 비어 있지 않은 힙의 값으로 교환할 수 있습니다. 먼저 비워진 힙에 따라 항상 왼쪽 힙 또는 적절한 힙이 됩니다.

이 알고리즘이 작동하려면 양 끝에서 효율적인 삽입 및 삭제를 지원하는 데이터 구조가 필요합니다. 이 데이터 구조는 또한 캐시 지역성을 활용할 수 있어야 합니다.