Можете ли вы помочь мне разобраться в этом алгоритме?

Question

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

Пусть L (1), L (2), .., L (k) - отсортированные списки по n элементов каждый. Задайте алгоритм пространства O (kn logk), который поддерживает операцию O (log n + t) Locate, которая возвращает местоположение элементов t.

В идеале, я смогу использовать этот алгоритм, чтобы дать мне некоторое представление о достижении лучшего решения (чего и требует назначение), но этот менее эффективный алгоритм должен вдохновлять меня, но я не могу понять это из. Есть мысли или знаете что это за алгоритм? Спасибо!

Answer 1

Вы гуглили на O (kn logk)? Кажется, это довольно уникальная подпись Big-O.

Вот мой первый результат: MergeSort -> Какова связь между слияниями и количеством элементов в слиянии в k-путях

Answer 2

Я не могу найти тот, который дает O (log n + t) времени, но у меня была мысль, которая может или не может помочь ...

O (kn log k) - размер таблицы, сопоставляющей каждый возможный элемент номеру списка, в котором он содержится. Тем не менее, использование этого для поиска списка для просмотра все еще приводит к времени поиска t * O (log n) для t элементов, так что это не совсем то, что запрашивается ...

Answer 3

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

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

Чтобы быть уверенным, что t вне logn, что-то вроде O ((logn) + t)?

Answer 4

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

Answer 5

Вероятно, не сортирующая функция, так как у вас уже есть 2 отсортированных списка. Для меня это звучит как бинарный поиск.

Answer 6

эхх ... звучит как ... бинарный поиск? Wiki