Поиск k-го наименьшего элемента в массиве с использованием quicksort => ожидаемого времени работы?

Question

Если я использую модифицированную версию quicksort для поиска k-го наименьшего элемента в массиве, почему ожидаемое время работы O (n) (как указано в книге Programming Pearls)?

алгоритм я использую делает следующее:

1) Runs quick sort on the array 
2) If k is > the correct location of pivot, then run quicksort on the 2nd half. 
Otherwise run it on the first half. 

Я был под впечатлением, это заняло бы O (N * LOGN) работы.

Answer 1

Эта ссылка может помочь понять доказательство рандомизированном быстрого выбора, http://pine.cs.yale.edu/pinewiki/QuickSelect,

Идея за получение Kth порядка статистика , выберите точку поворота и разделите данные, как это было предложено путем быстрой сортировки, и выясните, какой раздел находится в элементе поиска. . Разделение имеет сложность O (n). После разметки вам нужно выбрать только один из результирующего раздела для дальнейшей обработки в отличие от быстрой сортировки, где вам нужно обрабатывать оба.

В приведенном ниже описании, я не пытаюсь доказать, но хотел дать интуитивное мысли, чтобы понять ожидаемую сложность,

Для простоты допустим, на каждой итерации, стержень разбивает массив на равные части , то сложность явно O (п), а

n + (n/2) + (n/4) ... <= c.n, O(n) 

для интуитивного понимания, получая наихудшее секционирование, где вы должны обработать (N-1) элементы в каждой итерации происходит с вероятностью просто (1/п). Таким образом, сложность худшего случая в любом случае равна O (n^2).

В любом случае, если вы хотите строгое доказательство ожидаемой сложности, вы можете пройти через предоставленную ссылку.

Answer 2

Это не будет алгоритм, описанный в книге. Скорее это один раздел в (1), (2) и т.д.