我读到快速选择的时间复杂性是：
T(n) = T(n/5) + T(7n/10) + O(n)
我把上面的内容理解为"从n个元素中快速选择所需的时间=(从7n/10个元素中选择所需时间)+(从n/5个元素中进行快速选择所花费的时间)+">
所以我知道，一旦我们找到合适的枢轴，只剩下7n/10个元素，而安排一轮枢轴需要时间。
但n/5部分让我很困惑。我知道这与中位数有关，但我不太明白。根据我的理解，中位数的中位数是递归地分成5，然后找到中位数，直到你得到1。
我发现做这件事所花的时间大约是n所以妈妈的T(n)=n
你如何将quick_select(n)的T等于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)
有人能告诉我哪里出了问题吗？
在此设置中，T(n)是指在n个元素的数组上计算MoM所需的步骤数。让我们一步一步地研究算法，看看会发生什么。
首先，我们将输入分解为大小为5的块，对每个块进行排序，形成这些块的中值的新数组，并递归调用MoM来获得该新数组的中值。让我们看看每个步骤需要多长时间：
-
将输入分解为大小为5的块：这可以在时间O(1)内完成，只需隐式地将数组划分为块，而不移动任何东西。
-
对每个块进行排序：对任何常量大小的数组进行排序都需要时间O(1)。有O(n)个这样的块(具体地说，⌈n/5⌉)，所以这需要时间O(n)。
-
获取每个块的中值，并根据这些中值形成一个新的数组。每个块的中值元素可以在时间O(1)中通过只看中心元素来找到。存在O(n)个块，因此此步骤需要时间O(n)。
-
在该新数组上递归调用MoM。这需要时间T(⌈n/5⌉)，因为我们正在对上一步中形成的大小的数组进行递归调用。
因此，这意味着获得中值的实际中值的逻辑需要时间O(n)+T(⌈n/5⌉)。
那么T(7n/10)部分是从哪里来的呢？算法的下一步是使用我们在步骤(4)中找到的中值作为分割元素，将元素拆分为小于该枢轴的元素和大于该枢轴的单元。从那里，我们可以确定我们是否找到了要查找的元素(如果它在数组的右点)，或者我们是否需要在数组的左区域或右区域上递归。选择块中值的中值作为分割点的优点是，它保证了在该步骤中较小和较大元素之间的最坏情况下的70/30分割，因此，如果我们必须递归地继续算法，在最坏的情况下，我们使用大约7n/10个元素。
在中值部分的中值中，我们执行以下操作：
- 取子列表的中值，每个子列表最多有5个元素。对于这些列表中的每一个，我们都需要O(1)运算，并且有n/5个这样的列表，所以总共需要O(n)来找到它们中的每个的中值
- 我们取n/5个中位数中的中位数(中位数)。这需要T(n/5)，因为我们只需要检查n/5个元素
所以中间部分的中位数实际上是T(n/5)+O(n)，顺便说一句，T(7n/10)部分并不像你说的那样。