K-й элемент в неупорядоченном списке, использующий статистику порядка k - Временная сложность O (n)?

Question

Может кто-нибудь сказать мне, как алгоритм рандомизированного выбора дает среднюю сложность времени O (n)?Я вижу, что он будет иметь лучший вариант O (n), если случайно выбранный круг (во время 1-го прохода) является k-м элементом в спискеНо как это может быть средний случай?мы не можем гарантировать, что каждый раз, когда мы запустим алгоритм, мы попадем в правильный в первом проходе самого rt?

Answer 1

После выбора случайной позиции и разделения текущего диапазона мы знаем, находится ли k-й элемент слева или справа.Затем мы используем алгоритм с одной стороны.Таким образом, мы имеем сложность в среднем T (n) = n + T (n / 2), (n для разбиения).Таким образом, мы имеем O (n) в среднем

Answer 2

После первого прохода вы знаете, в какой «половине» будет k-й элемент. Теперь вы повторяете процесс для этой «половины» и т. Д.

Таким образом, в среднем случае в первой итерации вы делаете n шагов, во вторых n / 2 шага, затем n / 4 шага и так далее. В качестве обратной части расчета огибающей предположим, что n = 2 ** k. Общее количество шагов будет

2**k + 2**k/2 + 2**k/4 + ... = 2**k + 2**(k-1) + 2**(k-2) + ... + 2 + 1 
                             = 2**(k+1) - 1 
                             = 2n - 1

Итак, алгоритм O (2n - 1) = O (n).