O (n) алгоритм сортировки

Question

Это вопрос домашнего задания, поэтому я хотел бы избежать полных ответов и предпочел бы подсказки, если это возможно.

Учитывая массив случайных целых чисел A [1 ... x], программа должна вернуть первые элементы массива y в порядке увеличения, где 1 <= y <= sqrt (x). Итак, в основном, учитывая массив [5,9,2,8] и y = 2, программа должна вернуть [2,5]. </p>

Ответ "отсортировать сначала, вернуть первые y элементов" отсутствует в окне, так как лучшее, что мы можем сделать, это n * logn time с объединением или быстрой сортировкой. Таким образом, в ответе должен использоваться тот факт, что мы возвращаем только самое большее sqrt (x) элементов, и единственный другой ответ, который у меня есть, - это поиск цикла за минимальным элементом в массиве, удаляя минимум из массив, сохраняя его в новом массиве, скажем, B, и повторяя процесс для теперь уменьшенной модифицированной версии A длиной x-1, что дает нам время выполнения следующим образом:

x + (x-1) + (x-2) + ... + (x-y)

Это подсчитывает количество итераций цикла for в минимальном поиске и дает нам самое большее y или sqrt (x) итераций в худшем случае, и в массиве есть не более x элементов. Таким образом, мы имеем sqrt (x) * x, который лучше, чем O (n * logn), но все еще не совсем O (n): /.

Answer 1

Подсказка: предположим, у вас был O (n) алгоритм времени, чтобы выбрать элемент y ^th ...

Answer 2

Вы хотите только подсказку, верно?

Прочтите комментарий random_hacker очень внимательно, если вы пропустили большой намек, который он дает.Существует один алгоритм сортировки массива, в котором крошечные, крошечные изменения приведут к вашему алгоритму.

В общем, если y не ограничивается sqrt (x), вы получаете алгоритм, который работает в O (x + y * log x), который равен O (x), если y = O (x /log x), что, конечно, имеет место, когда y <= sqrt (x).</p>

Answer 3

Для y используйте идеи быстрой сортировки, выбрав случайное число и разделив его на 2 части.Часть 1 (меньше) и часть 2 (больше).Если длина Part1 y, выполнить разбиение в Part1 с использованием y' = y. Если длина Part1 == y, тоsort Part1.

Для разбиения среднее значение должно быть почти в O (n) (я не могу сейчас это одобрить, но это очень быстро) (я попытаюсь найти материал для этой части) ..Для сортировки по y требуется ylog (y) 1/2 * sqrt (x) * log (x) <1/2 * sqrt (x) * sqrt (x) => 1/2 х.

Answer 4

, где 1 <= y <= sqrt (x) </p>

Обратите внимание, что дает вам это требование.Если y ≤ √x, то y log y ≤ (√x log x) / 2 ∈ O (x ^½ log x) ⊂ O (x).

Sort-then-filterможет быть в окне, но filter-then-sort приемлемо.

Answer 5

На самом деле sqrt (x) растет быстрее, чем log (x), поэтому O (x * sqrt (x)) хуже, чем O (n * log (x)).Таким образом, вы (пока) не добились большего успеха, чем сортировка всего списка.

Есть несколько способов решить эту проблему.Для одного из них посмотрите на http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms и посмотрите на все распространенные алгоритмы сортировки.Какой алгоритм может дать вам первые несколько элементов наиболее эффективно?