O (регистрируют n), алгоритм для нахождения элемента, имеющего разряд i в объединении предварительно отсортированных списков
Учитывая два отсортированных списка, каждый содержащий n вещественные числа, там O (log n) алгоритм времени для вычислений элемента разряда i (где я соответствую индексу в увеличивающемся порядке) в объединении двух списков, предполагая, что элементы двух списков отличны?
Править: @BEN: Это я s, что я делал, но я все еще не получаю его.
У меня есть примеры;
Список A: 1, 3, 5, 7 списков B: 2, 4, 6, 8
Найдите разряд (i) = 4.
Первый шаг: i/2 = 2; Перечислите, теперь содержит, A: 1, 3 Списка B теперь содержат, B: 2, 4
compare A[i] to B[i] i.e
A[i] is less;
So the lists now become :
A: 3
B: 2,4
Второй Шаг: i/2 = 1
List A now contains A:3
List B now contains B:2
NoW I HAVE LOST THE VALUE 4 which is actually the result ...
Я знаю, что пропускаю некоторую вещь, но даже после близко ко дню размышления я не могу просто понять этого...
4 ответа
Да:
Вы знаете, что элемент находится в пределах индекса [0, i] первого списка или [0, i] второго списка. Возьмите элемент i / 2 из каждого списка и сравните. Продолжить делением пополам.
Я не включаю код, потому что эта проблема очень похожа на домашнее задание.
РЕДАКТИРОВАТЬ: Разделение пополам - это метод двоичного поиска. Это работает так:
Предположим, что i = 10; (индексирование с нуля, мы ищем 11-й элемент в целом).
На первом этапе вы знаете, что ответ находится либо в списке1 (0 ... 10), либо в списке2 (0 ... 10). Возьмем a = list1 (5) и b = list2 (5).
Если a> b, то есть 5 элементов в list1, которые идут перед a, и по крайней мере 6 элементов в list2, которые идут перед a. Таким образом, а - это верхняя граница результата. Точно так же есть 5 элементов в list2, которые идут перед b, и менее 6 элементов в list1, которые идут перед b. Итак, b - это нижняя граница результата. Теперь мы знаем, что результат находится либо в списке1 (0..5), либо в списке2 (5..10). Если a Мы просто повторяем этот процесс, сокращая размер области поиска вдвое на каждом шаге. Биссектриса относится к тому факту, что мы выбираем средний элемент (биссектрису) из диапазона, который, как мы знаем, включает результат. Таким образом, единственная разница между этим и двоичным поиском состоит в том, что в двоичном поиске мы сравниваем со значением, которое ищем, а здесь мы сравниваем со значением из другого списка. ПРИМЕЧАНИЕ: на самом деле это Кроме того, если i> n, то полагайтесь на тот факт, что результат должен быть ближе к концу любого списка, ваш начальный диапазон кандидатов в каждом списке будет от ((in) .. n) O (log i) , что лучше (по крайней мере, не хуже), чем O (log n) . Кроме того, для малых i (возможно, i <100) на самом деле было бы меньше операций для объединения первых i элементов (линейный поиск вместо деления пополам), потому что это намного проще. Когда вы добавляете поведение кеша и локальность данных, линейный поиск может быть быстрее для i до нескольких тысяч.
Вот как вы это делаете.
Пусть первый список будет ListX , а второй список будет ListY . Нам нужно найти правильную комбинацию ListX [x] и ListY [y] , где x + y = i . Поскольку x, y, i - натуральные числа, мы можем сразу же ограничить область нашей задачи до x * y . Используя уравнения max (x) = len (ListX) и max (y) = len (ListY) , мы теперь имеем подмножество x * y элементы в форме [x, y] , которые нам нужно искать.
Вы должны упорядочить эти элементы следующим образом: [i - max (y), max (y)] , [i - max (y) + 1, max (y) - 1] , ..., [max (x), i - max (x)] . Затем вы разделите этот список пополам, выбрав среднюю комбинацию [x, y] . Поскольку списки упорядочены и различны, вы можете протестировать ListX [x] [x, y] , а если ложь, то мы делим пополам нижнюю половину. Вы будете продолжать делить пополам, пока не найдете правильную комбинацию.
Я оставил много деталей, но в этом вся суть. Это действительно O (log (n))!
Изменить: Как сказал Бен, на самом деле это O (log (i)) . Если мы положим n = len (ListX) + len (ListY) , то мы узнаем, что i <= n .
При объединении двух списков вам нужно будет коснуться каждого элемента в обоих списках. Если не трогать каждый элемент, некоторые элементы останутся позади. Таким образом, ваша теоретическая нижняя граница - O (n). Так что вы не можете этого сделать.
Вам не нужно сортировать, так как у вас есть два списка, которые уже отсортированы, и вы можете сохранить этот порядок как часть слияния.
edit: ой, я неправильно понял вопрос. Я думал, что учитывая ценность, вы хотите получить звание, а не наоборот. Если вы хотите найти заданное значение ранга, то это можно сделать в
O (журнал N):
Да, вы можете сделать это в O (журнал N) , если список разрешает O (1) произвольный доступ (т.е. это массив, а не связанный список).
- Двоичный поиск на L1
- Двоичный поиск на L2
- Суммирование индексов
Вам придется вычислить, +1, -1, что делать, если элемент не найден и т. Д. , но это идея.