Нахождение нижней границы по временной сложности нахождения k пар

Question

Нам даны n болтов и гаек разных размеров, где каждый болт точно соответствует одной гайке. Наша цель - найти подходящую гайку для каждого болта. Гайки и болты слишком похожи, чтобы сравнивать напрямую; однако мы можем проверить, слишком ли большой гайка, слишком мал или такой же размер, как и любой болт.

Докажите, что в худшем случае для определения совпадающих пар необходимо сопоставить гайковерты Ω (n + k log n).

Я полностью зациклен на том, как это сделать, я рисую трехмерное дерево решений, для чего понадобятся n^k узлов, что дает klog (n) для высоты дерева, но я могу " t выяснить, откуда приходит + n.

Answer 1

Вот очень свободный ответ, который мог бы стать основой надлежащего доказательства:

Предположим, что вы должны спросить меня (ваш противник) каждый раз, когда вы хотите, чтобы проверить новую гайку или новый болт и я дайте вам новую гайку или новый болт. Перед началом работы я сортирую гайки и болты в соответствующие пары, а затем разделяю пары на две кучи, каждый размером n/2. Для первых n/2 шагов я даю вам орех из первой кучи или болт со второй кучи, в зависимости от того, что вы просите. Поэтому я всегда могу отложить вас от поиска любых совпадений, пока вы не выполнили хотя бы n/2 попытки совпадения, потому что до тех пор, пока я не выйду из одной из кучек, вы никогда не получите гайку и болт, которые соответствуют.

Ваша жизнь не будет сложнее, если я помечаю болты в порядке их размера, потому что вы всегда можете игнорировать эту информацию. Теперь, если вы можете найти k совпадений во времени меньше, чем k log n, для всех возможных k и n> = k вы можете решить проблему сортировки n чисел, используя только сравнения, где, как известно, числа являются множеством {1 , 2,3 ... N}. На самом деле, даже если у вас есть волшебный метод, который работает только для, например, k < = 3 и все n, вы все равно можете выполнить эту сортировку с низким уровнем сравнения, повторно обнаружив 3 совпадения между установленными (немаркированными) гайками и набором (помеченных) болтов. Поэтому, если вы можете найти совпадения с меньшим, чем k log n сравнением, вы можете отсортировать числа, известные как {1,2 ... n} с меньшим, чем n log n сравнениями, - но обычная информационная теоретическая нижняя граница сортировки здесь. Таким образом, вам нужно как минимум k log n сравнению.

Итак, теперь мы имеем нижнюю границу max (n/2, k log n). Нам не нужны факторы, поэтому давайте будем иметь max (n, k log n). Но (a + b)/2 < = max (a, b) < = a + b для a, b> = 0, поэтому снова пренебрегая факторами, мы можем превратить это в n + k log n.