Блог

Учитывая отсортированный массив A [1..n] и положительное целое число k, подсчитайте количество целых чисел в интервалах (100 (i-1) / k, 100 (i) / k] для 1 <= i <= k и сохраните его в другом массиве G[1..k]

Предположим, что массив G уже создан (не является входом в алгоритм), а элемент в G инициализирован равным 0.

Кроме того, существует вспомогательная функция Increase(i, count), чтобы найти интервал (G [?]), которому соответствует [i], и увеличить значение G[?] на count;

Например, отсортированный массив [1,11,25,34,46,62,78,90,99] и k = 4

таким образом, результат должен быть G[1] = 3, G [2] = 2, G [3] = 1, G [4] = 3, где G [1] — интервал (0,25] G[2] -> (25,50] G [3] -> (50,75] G[4] -> (75,100]

Существует ли какой-либо алгоритм «разделяй и властвуй» для решения этой проблемы? вместо того, чтобы решать его линейно?

Более продвинутый: также, если мы не можем напрямую получить доступ к элементу в массиве A , и есть функция Compare(x, y) для возврата true, если A[x] и A[y] находятся в одном и том же интервале. Как это решить? Могу ли я попытаться увеличить время каждого группового вызова не более чем за журнал n, и, следовательно, существует k групп, имеющих время выполнения O (k log n)?

Мое наблюдение на данный момент: если A [i] и A[y] находятся в одном и том же интервале, где i < y, элемент A[j] с i < j < y также будет в том же интервале.

Самый простой сублинейный подход (при условии, что k << n) заключается в выполнении (k 1) двоичных поисков, по одному для каждого граничного значения, что дает приблизительно (k lg n) -алгоритм сравнения.

Это может быть уменьшено примерно до (k (1 lg (n / k))) путем разумного объединения зондов вместе.