Среднее количество интервалов от входа в 0..N

Вопрос возник при рассмотрении вопроса "Найти K пропущенных чисел в этом наборе, который должен охватывать [0..N]".

Автор вопроса попросил ответы CS вместо ответов на основе уравнений, и его предложение состояло в том, чтобы отсортировать входные данные, а затем выполнить итерацию по ним, чтобы перечислить K пропущенных чисел.

Хотя это кажется мне подходящим, это также кажется расточительным. Давайте возьмем пример:

  • N = 200
  • К = 2 (рассмотрим К << Н)
  • недостающие элементы: 53, 75

"Сортированный" набор может быть представлен как: [0, 52] U [54, 74] U [76, 200], что намного компактнее, чем перечисление всех значений набора (и позволяет извлечь пропущенные числа в операциях O(K), для сравнения с O(N), если набор отсортирован).

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

Поэтому давайте введем еще одну переменную: пусть I быть количеством элементов набора, который мы передали в структуру до сих пор. Тогда в худшем случае мы можем иметь: min((N-K)/2, I) интервалы (я думаю...)

Из чего мы выводим, что число интервалов, достигнутых во время построения, является максимумом, встречающимся для I в [0..N], наихудший случай (N-K)/2 таким образом O(N),

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

Сколько интервалов... в среднем?

Источник

1 ответ

Ваш подход против предложенного с сортировкой кажется классическим компромиссом, какие операции дешевы, а какие дорогостоящи.

Я нахожу вашу запись немного запутанной, поэтому, пожалуйста, позвольте мне использовать мою собственную:

Позволять S быть набором. Позволять n быть количеством предметов в наборе: n = |S|, Позволять max быть самым большим числом в наборе: max = max(S), Позволять k быть количеством элементов не в наборе: k = |{0,...,max} \ S|,

Для решения сортировки мы могли бы очень дешево вставить все n элементы в S используя хеширование. Это займет ожидаемое O(n), Тогда для нахождения k отсутствующие элементы, мы сортируем множество в O(nlogn), а затем определить недостающие элементы в O(n),

То есть общая стоимость добавления n элементы, а затем найти недостающие k элементы занимает ожидаемое O(n) + O(nlogn) + O(n) = O(nlogn),

Вы предлагаете другой подход, в котором мы представляем набор в виде списка плотных подмножеств S, Как бы вы реализовали такую ​​структуру данных? Я предлагаю отсортированное дерево (вместо списка), чтобы вставка стала эффективной. Потому что вы должны сделать для вставки нового элемента e? Я думаю, что вы должны:

  1. Найдите потенциальное подмножество кандидатов в дереве, где e можно добавить
  2. Если подмножество уже содержит eничего не надо делать.
  3. Если подмножество содержит e+1 и другое подмножество содержит e-1, объединить подмножества вместе и добавить e к результату
  4. Если подмножество уже содержит e+1, но e-1 не содержится в S, добавлять e к этому подмножеству
  5. Если подмножество уже содержит e-1, но e+1 не содержится в S, добавлять e к этому подмножеству
  6. В противном случае создайте новое подмножество, содержащее только элемент e и вставьте его в дерево.

Можно ожидать, что поиск подмножеств, необходимых для вышеуказанных операций, занимает O(logn), Операции 4. или 5. занимают постоянное время, если мы представляем подмножества в виде пар целых чисел (мы просто должны уменьшить нижнюю или увеличить верхнюю границу). 3. и 6. потенциально требуют изменения древовидной структуры, но мы ожидаем, что это займет максимум O(logn)поэтому вся "вставка" не займет больше O(logn),

Теперь с такой структурой данных мы можем легко определить k пропущенные числа путем обхода дерева по порядку и сбора чисел, не входящих ни в одно из подмножеств. Затраты линейны по количеству узлов в дереве, которое <= n/2Таким образом, общие расходы O(n) для этого.

Однако, если мы снова рассмотрим полную последовательность операций, мы получим для n вставки O(nlogn) + O(n) для нахождения k пропущенных чисел, поэтому общие затраты снова O(nlogn),

Это не лучше, чем ожидаемые затраты на первый алгоритм.

Третье решение заключается в использовании логического array представлять множество и одно целое число max для самого большого элемента в наборе.

Если элемент e добавлен в набор, вы устанавливаете array[e] = true, Вы можете реализовать переменный размер набора, используя расширение таблицы, поэтому затраты на вставку элемента в массив постоянны.

Чтобы получить недостающие элементы, вы просто собираете эти элементы f где array[f] == false, Это займет O(max),

Таким образом, общие затраты на вставку n элементов и нахождение k пропущенных элементов составляют: O(n) + O(max), Тем не мение, max = n + kи так мы получаем как общие расходы O(n + k),

Четвертый метод, который представляет собой переход между третьим и тем, который использует хеширование, является следующим, который также использует хеширование, но не требует сортировки.

Храните свой набор S в хэш-набор, а также хранить максимальный элемент в S в переменной max, Чтобы найти k пропущенные, сначала сгенерируйте результирующий набор R, содержащий все числа {0,...,max}, Затем перебрать S и удалить каждый элемент в S от R,

Расходы на это также O(n + k),

Источник
Другие вопросы по тегам