线性时间选择问题提出是如何在最坏情况下用线性时间在一 个包含 n 个元素的线性序集中找到第 k 小元素。 1. 为什么采用的 randomizedSelect 算法无法保证在最坏情况下可 以用O n( )线性时间找到第 k 小元素?

### 回答1：
随机化算法的时间复杂度是平均情况下的复杂度，而不是最坏情况下的复杂度。在最坏情况下，随机化算法可能会选择到最坏的情况，导致时间复杂度变高。因此，随机化算法无法保证在最坏情况下可以用线性时间找到第 k 小元素。

### 回答2：
线性时间选择问题是指在一个包含 n 个元素的线性序集中找到第 k 小的元素。其中一种解决方案是采用 randomizedSelect 算法。

randomizedSelect 算法的思路是通过随机选取一个主元(pivot)将序列分为两部分，并将主元放置在它在排序后应该在的位置上，然后根据主元所在的位置与 k 的关系，递归地在子序列中进行查找。

然而，randomizedSelect 算法无法保证在最坏情况下可以用线性时间找到第 k 小的元素。这是因为在不幸的情况下，主元的选择可能使得每次划分的两个子序列的大小相差很大，导致算法的效率降低。比如，当每次的主元都选取为已有序集合的最大或最小元素时，算法会达到最坏情况。

在最坏情况下，randomizedSelect 算法的时间复杂度为O(n^2)，而不是线性时间复杂度O(n)。这是因为每次递归调用都会需要O(n)的时间复杂度来找到主元的位置，并且递归的深度可能会达到n个，导致总的时间复杂度为O(n^2)。

因此，为了保证在线性时间内找到第 k 小的元素，可以考虑使用其他的算法，如快速选择算法或者堆选择算法。这些算法在最坏情况下仍然可以保持线性时间复杂度，并且具有更好的性能表现。

### 回答3：
在随机化选择算法中，我们通过随机选择一个主元将集合分成小于和大于主元的两个子集。然后，我们可以确定第 k 小的元素在哪个子集中，从而继续在该子集中递归地查找第 k 小的元素。

在最理想的情况下，每次都能选择到一个中位数作为主元，那么每次分割后的子集大小会近似地减半。根据这个性质，我们可以得到一个递归式 T(n) = T(n/2) + O(n)，其中 T(n) 表示找到第 k 小元素所需的时间。

然而，在最坏情况下，我们可能始终无法选到一个合适的主元，导致递归过程中子集的大小没有明显减小。例如，如果每次选择的主元都是当前子集的最大值，那么递归过程将无法将子集的大小减半。在这种情况下，递归过程需要进行 n-1 次递归调用，并且每次查找一个最大值需要 O(n) 的时间。因此，在最坏情况下，随机化选择算法的时间复杂度为 O(n^2)。

因为随机化选择算法并不能保证在最坏情况下能够用线性时间找到第 k 小的元素，所以我们需要使用其他方法来解决这个问题。一种常用的方法是使用类似快速排序的思想，在每次递归中根据划分的结果决定继续在哪个子集中查找第 k 小元素。这种方法称为中位数的中位数算法，时间复杂度为 O(n)，可以在最坏情况下保证找到第 k 小元素。