Временная сложность быстрого выбора

Question

Я читал, что временная сложность быстрого выбора является:

T(n) = T(n/5) + T(7n/10) + O(n) 

Я прочитал выше вещь, как «время, необходимое для быстрого выбора из п элементов = (время, необходимое для выбора 7n/10 элементов) + (время, необходимое для быстрого выбора из n/5 элементов) + (некоторая константа * n) "

Итак, я понимаю, что как только мы найдем приличную ось, осталось только 7n/10 элементов и сделать один раунд для размещения свода требуется время n.

Но часть n/5 меня смущает. Я знаю, что это связано с медианной средой, но я не совсем понимаю ее. медиана медиан от того, что я понял, рекурсивно разделив на 5 и нахождение медианы, пока у получить 1.

я обнаружил, что время, чтобы сделать это, о п Так T мамы (п) = n

Как вы приравниваете T к quick_select (n) = T_mom (n)/5?

Другими словами, это то, что я думаю, что уравнение следует читать:

T(n)= O(n)+n+T(7n/10) 
where, 
O(n) -> for finding median 
n-> for getting the pivot into its position 
T(7n/10) -> Doing the same thing for the other 7n/10 elements. (worst case) 

Может кто-нибудь сказать мне, где я неправильно?

Answer 1

В среднем средней части, мы делаем следующее:

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

Таким образом, медиана медианной части на самом деле равна T (n/5) + O (n), BTW часть T (7n/10) не совсем так, как вы сказали.

Answer 2

В этой настройке T (n) относится к числу шагов, необходимых для вычисления MoM в массиве из n элементов. Давайте рассмотрим алгоритм один шаг за раз и посмотрим, что произойдет.

Сначала мы разбиваем входные данные на блоки размером 5, сортируем каждый блок, формируем новый массив медианов этих блоков и рекурсивно вызываем MoM, чтобы получить медиану этого нового массива. Давайте посмотрим, как долго каждый из этих шагов принимает:

1. Перерыв вход на блоки размером 5: это может быть сделано за время O (1), только неявно разбиении массива на блоки, не двигая ничего.

2. Сортировка каждого блока: сортировка массива любого постоянного размера занимает время O (1). Существуют такие O (n) такие блоки (в частности, ⌈ n/5 ⌉), так что это занимает время O (n).

3. Получите медиану каждого блока и сформируйте новый массив из этих медианов. Медианный элемент каждого блока можно найти во времени O (1), просто посмотрев на элемент центра. Существуют блоки O (n), поэтому этот шаг занимает время O (n).

4. Рекурсивно вызывать MoM на этом новом массиве.Это требует времени T (⌈ n/5 ⌉), так как мы делаем рекурсивный вызов массива такого размера, который мы сформировали на предыдущем шаге.

Таким образом, это означает, что логика, чтобы получить фактический алгоритм выбора требует времени O (п) + T (⌈ п/5 ⌉).

Итак, откуда взялась часть T (7n/10)? Ну, следующий шаг в алгоритме состоит в том, чтобы использовать медиану медианов, найденную на этапе (4), в качестве элемента разделения, чтобы разбить элементы на элементы, меньшие, чем эта ось, и элементы, которые больше, чем эта ось. Оттуда мы можем определить, нашел ли мы элемент, который мы ищем (если он находится в нужном месте в массиве), или нам нужно перезаписать левую или правую области массива. Преимущество выбора медианы медианов в блоке как точки расщепления заключается в том, что он гарантирует наихудший разрыв 70/30 на этом этапе между меньшими и более крупными элементами, поэтому, если нам приходится рекурсивно продолжать алгоритм, в худшем мы делаем это примерно с 7n/10 элементами.