Алгоритм-поиск kth следующего элемента в массиве

Я не мог решить вопрос, можете ли вы помочь?Алгоритм-поиск kth следующего элемента в массиве

For i=1 to i=n/2, if A[i]<=A[2i] and A[i]<=A[2i+1] A is called as a "bst"

Что временная сложность для нахождения kth наименьшего элемента в bst с п элементов?

источник

2015-06-14 Enes Erciyes

Вы уверены это не должно быть A [i] <= A [2i + 1] и A [i] <= A [2i + 2] '? Если это так, это двоичная куча, и вы можете найти k'th наименьший элемент в O (k) – amit

То, что я пишу, именно то, что он задает –

Это ваша домашняя работа? (репирический вопрос) – ale64bit

Я могу сделать это в O(klogk) и при условии, что k<<n - это будет довольно эффективно по сравнению с альтернативами.

Идея состоит в том, чтобы поддерживать минимальную кучу, начинать с головы (id == 0), которая является самым низким элементом, и итеративно добавлять все «новые кандидаты» (которые для данного текущего наименьшего i - «кандидаты» - 2i и 2i+1).

Создайте новый пустой мин-кучу, в которой каждый элемент содержит tupple (х, я) - х ключ в массиве, и я это индекс

set i = 0, currIdx = 0 
heap.add((i,0)) 
while currIdx < k: 
currIdx = currIdx + 1 
    (x,i) = heap.popLowest() 
    if i != 2i: //for i=2i=0, don't add it twice: 
     heap.add((arr[2i],2i)) 
    heap.add((arr[2i+1],2i+1)) 
return heap.getTop()

Время сложность O(klogk), каждый работа на куче принимает O(logN) (где N - его текущий размер), а куча растет до максимального размера N=k, поэтому все операции на куче log(1) + log(2) + ... + log(k) = log((k)!), что находится в O(klogk).

источник

2015-06-14 07:38:35 amit

Это хороший способ, но, на удивление, это можно сделать в O (k) времени (как вы говорите в своем комментарии, но не в этом ответе ...?): Http://dl.acm.org/citation .cfm? ID = 176014. Я еще не читал всю статью, но это кажется сложным и техническим, и я нахожу его ошеломляющим, что студенты должны были придумать такие вещи (открытую проблему в CS до 1992 года!) С нуля в ограниченных по времени условиях ! –

Есть два способа:

вывода (к п (п)) временная сложность.
O (k ln (k)) сложность по времени + O (K) пространственная сложность.

источник

2015-06-14 07:47:00

Во-первых, вы имеете в виду «кучу», а не «bst» (структура данных, которую вы описали, обязательно является кучей и не обязательно является bst).

Во-вторых, совершенно очевидно, что эта проблема разрешима в O (k) времени - только в 1992 году это было Frederickson gave an O(k)-time algorithm for this. Я не читал эту статью на всем протяжении, но это 18 страниц сложного технического аргумента, и я поражен тем, что организаторы Олимпиады ожидали, что студенты по существу придумают это с нуля! (Или, может быть, они ожидают, что они уже знакомы с алгоритмом - в этом случае я бы сказал, что (а) он все еще задает довольно много, и (б) это не очень хороший вопрос.)

источник

2015-06-15 14:00:01

Алгоритм-поиск kth следующего элемента в массиве

ответ

Смежные вопросы