Изменение алгоритма рандомизированного выбора влияет на время выполнения - PullRequest
Новая
       37

Изменение алгоритма рандомизированного выбора влияет на время выполнения

0 голосов
/ 31 октября 2019

Что случится со временем выполнения алгоритма рандомизированного выбора, если мы изменим строку 8 в коде с q-1 на q на странице книги CLRS 216?

Я обнаружил, что алгоритм все еще должен работать и не долженНе должно быть никаких изменений во времени выполнения, поскольку это зависит только от подпрограммы RANDOMIZED PARTITION. Это правда? 

Randomized-Select (A,p,r,i)
// Finds the ith smallest value in A[p .. r].
if (p = r)
    return A[p]
q = Randomized-Partition(A,p,r)
k = q-p+1   // k = size of low side + 1 (pivot)
if (i = k)
    return A[q]
else if (i<k)
    return Randomized-Select(A,p,q-1,i)
else
    return Randomized-Select(A,q+1,r,i-k)

1 Ответ

1 голос
/ 31 октября 2019

I-я статистика может быть в:
левой части - диапазоне p ..q-1
правой части - диапазоне q + 1..r
точно по индексу q

Последний случай случается, когда условие выполняется: 

if (i = k)
   return A[q]

в противном случае мы знаем, что q-й элемент никогда не будет i-й статистикой, поэтому нецелесообразно обрабатывать его снова и снова на более поздних итерациях (рекурсияуровни).

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

(средний случай n + n/2 + n/4 + ... + 1=2n против n + (n/2+1) + (n/4+1) + ... + 1=2n+log(n))

...