Индексирование членства в постоянное время для интервалов на реальной линии?

Question

Скажем, мне дали набор весов, составляющих до 1, и я выстроил их один за другим, чтобы сделать серию бункеров, длина которых пропорциональна их весу. Я присваиваю каждому бину целое число, соответствующее его месту в строке.

Учитывая любое число в [0,1], я хотел бы иметь возможность проверить, какой индекс соответствует корзине, в которую попадает это число. Могу ли я придумать алгоритм, чтобы сделать это в постоянное время?

Решение логарифмического времени является простым, но я надеюсь на лучшее!

Answer 1

Это, вероятно, может быть выполнено с использованием псевдонима , который можно использовать для генерации случайных выборок из дискретного распределения за время O (1). Я полагаю, что вы можете адаптировать этот алгоритм для решения своей проблемы, просто инвертировав преобразование, чтобы вместо отображения из равномерной случайной переменной в дискретную группу вы отображали из дискретной группы в единую переменную. Оттуда вы можете определить, в какой сегмент попадает значение.

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ : Недавно я написал обширную статью о методе псевдонимов и других связанных трюках. Надеемся, что это делает алгоритм и его интуицию понятнее и проще!

Answer 2

Создайте таблицу с k записями, и 1 / k должно быть меньше вашей самой маленькой записи. Затем вы заполняете таблицу записями, на которые они указывают, и тогда у вас есть O (1).

Если вы ослабите ограничение на k, вы можете создать многоэтапный поиск, где первый шаг такой же, как и выше, но второй шаг - это линейный или логарифмический поиск. Это тогда становится O(log2(n/k)). n/k, k=n => O(log2(1)) = O(1)?

Чтобы найти, какую запись в таблице использовать, это слово floor (x * k)