Алгоритм сортировки и спаривания элементов 2 массивов

Question

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

Редактировать: элементы массивов имеют «размеры», которые соответствуют конкретным объектам. Идея состоит в том, что две части одного размера будут соответствовать друг другу. Если бы мы назвали детали винтами и отверстиями, винт поместится только в отверстие того же размера. Однако мы не можем сравнивать отверстия с отверстиями или винты с винтами для целей этого алгоритма.

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

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

Answer 1

Пересмотренный

Предположим, что мы можем получить один из трех результатов, когда попытаемся вставить винт в отверстие:

1. Винт слишком мал для отверстия, так что винт ослаблен и выпадает.
2. Винт точно соответствует отверстию.
3. Винт слишком большой для отверстия.

Разделяй и властвуй решение.

• Этап № 1
  1. Выберите один винт.
  2. Используйте этот винт для проверки всех отверстий. (требуется N испытаний)
     • Это делит все отверстия на один из трех случаев:
       1. Отверстие больше контрольного винта (A).
       2. Отверстие того же размера, что и контрольный винт (B).
       3. Отверстие меньше контрольного винта (C).
  3. Используйте отверстие одинакового размера (выбрано из B) для проверки всех винтов. (требуется N испытаний)
     • Это делит все винты на один из трех случаев:
       1. Винт больше контрольного отверстия (D).
       2. Размер винта совпадает с размером испытательного отверстия (E).
       3. Винт меньше контрольного отверстия (F).
     • Результат:
       1. Любое отверстие, выбранное из B, будет соответствовать любому винту, выбранному из E. Это будет «ось» перегородки. Они не требуют дальнейшего тестирования.
       2. Отверстия в наборе A и винты в наборе D имеют диаметры, более широкие, чем у оси. Отверстия в наборе C и винты в наборе F имеют диаметры уже, чем шарнир.
       3. Таким образом, мы успешно разбили начальную проблему на две меньшие задачи.

Анализ

• Средний регистр: O(N log N)
• Наихудший случай: O(N^2), потому что мы не знаем ранг пивота, пока не закончим разбиение множества с помощью пивота. Тот же анализ, что и QuickSort .

Об одном варианте вопроса

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

• отверстие < винт
• отверстие >= винт

Этот вариант намного сложнее. Я не знаю, может ли это быть решено в O(n log n) или нет. (Edited)

Answer 2

Если вы не можете сравнить «винты» с другими «винтами» или «отверстиями» с другими «отверстиями», то ни массив «винтов», ни массив «отверстий» не могут быть отсортированы. Я думаю, это означает, что вы должны сравнить данный «винт» с каждым «отверстием» по очереди, чтобы найти совпадение. Это O(N^2).

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

EDIT

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

[То есть ... если только вы не сортируете все "отверстия" по тому, меньше ли они, больше или подходят для данного "винта". Но это операция O(N) ... сортировка ведра ... и вам нужно сделать это для каждого винта, чтобы вы вернулись к O(N^2). Я полагаю, что этот подход может помочь, если вы выполняли этот процесс сопряжения постепенно. Но ты этого не говорил.]

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