Как разработать эффективный алгоритм поиска наименьшей верхней границы

Question

Допустим, у вас есть некоторый набор чисел с известной нижней границей и неизвестной верхней границей, то есть 0, 1, 2, 3, ... 78, где 78 - неизвестное. Предположим, на данный момент между числами нет пробелов. Существует дорогостоящая функция test(), которая проверяет, есть ли число в наборе.

Как эффективный способ (требующий небольшого количества вызовов test()) найти самый большой номер в наборе?

Что если у вас есть дополнительное знание, что верхняя граница составляет 75 +/- 25?

Что, если между числами в наборе есть случайные промежутки, то есть 0, 1, 3, 4, 7, ... 78?

Answer 1

Для «без пропусков»:

• Я предполагаю, что это фиксированный размер числа, например 32-битный int
• Мы хотим найти x такой, что test(x) == true, test(x+1) == false, верно?

В основном вы выполняете двоичное разбиение между самым низким известным"не в наборе" (например, самым большим 32-битным целым числом) и самым высоким известным"в наборе" (начиная с известная нижняя граница), каждый раз проверяя среднее значение в диапазоне и соответственно корректируя границы. Это дало бы решение O(log N) (в терминах количества вызовов test()), где X - это размер набора потенциальных , а не фактический установлено. Это будет медленнее, чем просто пробовать 1, 2, 3 ... для маленьких наборов, но намного быстрее для больших.

Все это падает, если могут быть пропуски, и в этот момент я не думаю, что есть какое-либо реальное решение, кроме "начни с максимально возможного максимального числа и работай до test(x) == true, в котором это самое большое число" , Насколько я понимаю, любая другая стратегия потерпит неудачу или будет дороже.

Answer 2

1. Установите Step на 1
2. установить Upper на Lower + Step
3. , если test(Upper) истинно, тогда установите Lower на Upper, умножьте Step на 2 и перейдите к точке 2
4. на данный момент вы знаете, что Lower находится в вашем наборе, а Upper нет. Теперь вы можете выполнить двоичный поиск между Lower и Upper, чтобы найти предел.

Это похоже на сложность O (log n * O (test)).

Если вы знаете, что Upper находится между 50 и 100, выполните двоичный поиск между этими двумя значениями.

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

Если у вас есть случайные пробелы, и вы не знаете верхний предел, тогда вы можете никогда быть уверенным, что вы нашли верхнюю границу.

Answer 3

Лучше всего просто пробежаться по сету со сложностью O(n), что неплохо.

Примите во внимание, что набор не отсортирован (это, в конце концов, набор, и это дано), каждая операция isInSet(n) также требует O(n), что приводит к O(n^2) для всей операции , если вы выбираете какой-либо алгоритм для подталкивания набора в определенных местах ...

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

Answer 4

Если ваш набор окажется набором простых чисел, дайте мне знать, когда найдете наибольшее. Я уверен, что мы можем что-то решить. ;)

А если серьезно, я предполагаю, что вы точно знаете, что набор действительно имеет наибольшее значение. Или вы выбираете 32-битное целое число.

Пара предложений:

1) Подумайте о каждом случае, который может ускорить результат теста (x) == false. Тогда вы можете перейти к следующему. Если время, которое вы тратите на прохождение всех случаев выброса, намного меньше, чем на прохождение полного теста, тогда вы выйдете вперед. 2) Можете ли вы получить какую-либо информацию из каждого теста? Например, подразумевает ли test (x) == false, что test (x + 5679) == также false?

Answer 5

Если пробелов нет, то вам лучше всего использовать бинарный поиск.

Если мы используем второе предположение, что вершина равна 75 +/- 25, тогда нижний предел равен 50, верхний конец равен 100, а наш первый тестовый пример равен 75. Если он присутствует, то нижний конец 75 и верхний предел равен 100, и наш тестовый пример равен 87. Это должно дать результаты в O (ln N) (где здесь N будет 50).

Если мы не можем предположить возможный верхний диапазон, мы просто должны сделать обоснованное предположение о том, что это может быть. Если значение не найдено, оно становится верхним пределом. Если он найден, это нижний предел, и мы удваиваем его, чтобы найти верхний предел.

Если есть пробелы, я могу видеть только один способ - это линейный поиск, но даже тогда вам понадобится способ узнать, когда вы достигли конца, а не просто большой пробел.

Answer 6

Знаете ли вы установленный размер, перед рукой?

На самом деле, я думаю, что вы, вероятно, нет - в противном случае первая проблема будет тривиальной.

Было бы полезно, если бы вы знали, насколько велик был сет.

1. Догадайся по верхнему значению
2. Тест - если в этом случае увеличить значение на некоторую величину
3. Если нет, уменьшите значение на некоторое количество
4. Если у вас есть верхняя и нижняя границы для наибольшего значения, выполняйте бинарный поиск, пока не найдете его (с требуемой точностью).

Для пробелов у вас нет такой способности - вы даже не можете сказать, когда вы нашли самый большой элемент. (Если вы не знаете максимальный размер зазора)

Answer 7

Может быть, вам стоит пройти через это? Это будет O (n) комплекс. Я думаю, что нет другого способа сделать это.