延绪的水上书
0%

顺序统计量

发表于 更新于 分类于 Disqus：

最小值和最大值

在一个有 n 个元素的集合中，需要做多少次比较才能确定其最小元素呢？

最简单的方式：依次遍历集合中的每个元素，并记录下当前最小元素。这样会经过 n-1 次比较。进一步，如果我们希望同时找到最小值和最大值，如此方法则需要 2n-2 次比较。

但事实上，我们有更快速的方法，能同时找到最大值和最小值，且只需要 3[n/2] 次比较。

步骤如下：

  • 将输入元素成对处理。对于每一对元素 a 和 b，相互比较。
  • 将 a、b 中的较小者与当前最小值比较，将较大者与当前最大值比较。这样，每对元素需要3次比较。

在此基础上，比较次数可以进一步缩减到 **O(logn)**。

步骤如下：

  • 递归处理：每次能将最大值、最小值所在集合的范围缩小一半。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def find_min_max(arr):
    if not arr:
        return None, None  # 如果数组为空，返回None

    min_val = max_val = arr[0]
    start = 1

    while start < len(arr):
        # 如果数组长度是奇数，最后一个元素与当前最小值和最大值比较
        if start % 2 == 1:
            if start < len(arr) - 1:
                a, b = arr[start], arr[start + 1]
            else:
                a, b = arr[start], arr[start]
        else:
            a, b = arr[start], arr[start + 1]

        # 比较两个元素
        if a < b:
            if a < min_val:
                min_val = a
            if b > max_val:
                max_val = b
        else:
            if b < min_val:
                min_val = b
            if a > max_val:
                max_val = a

        start += 2  # 移动到下一对元素

    return min_val, max_val

# 示例
arr = [7, 2, 14, 11, 3, 5, 1, 9, 8, 4, 13, 6, 12, 10]
min_val, max_val = find_min_max(arr)
print("Minimum is", min_val)
print("Maximum is", m)

选择算法

在一个有 n 个元素的集合中，如何找到第 i 小的元素呢？

期望为线性时间的选择算法

RANDOMIZED-SELECT 是一个分治算法，用于在数组中找到第 i 小的元素。这个算法是基于快速排序的分区操作 RANDOMIZED-PARTITION 的，但它只递归地处理分区的一边，而不是两边。这使得 RANDOMIZED-SELECT 的期望运行时间为 **O(n)**，这比快速排序的 O(n · log n) 要好。

步骤如下：

  1. 边界检查：如果子数组的范围 p 和 r 相等，说明已经找到了第 i 小的元素，直接返回。
  2. 随机分区：使用 RANDOMIZED-PARTITION 对数组 A[p..r] 进行分区，返回分区的基准索引 q。
  3. 计算基准位置：计算枢轴元素相对于子数组起始位置 p 的位置 k。
  4. **比较 i 和 k**：如果 i 等于 k，则枢轴元素就是第 i 小的元素，返回 A[q]。如果 i 小于 k，则在左子数组 A[p..q-1] 中递归寻找第 i 小的元素。否则，在右子数组 A[q+1..r] 中递归寻找第 i-k 小的元素。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
RANDOMIZED-SELECT (A, p, r, i)
	if p==r
		return A[p]
	q = RANDOMliZED-PARTITION(A, p, r)
	k = q-p+1
	if i == k
		return A[q]
	else if i<k
		return RANOOMIZED-SELECT(A, p, q-1, i)
	else return RANOOMIZED-SELECT(A, q+l, r, i-k)

最坏情况为线性时间的选择算法

因为随机选可能很倒霉

我们给出一个选择算法 SELECT，最坏情况仍为线性时间。

步骤如下：

  1. 分组：将数组分为大约 n/5 组，每组包含5个元素。如果有剩余元素（即 n % 5 不为0），则形成最后一组。
  2. 寻找每组的中位数：对每组进行插入排序（或其他线性时间排序），然后选择每组的中位数。
  3. 递归寻找中位数的中位数：对所有组的中位数进行递归调用 SELECT 算法，找到它们的中位数 x。
  4. 划分数组：使用 x 作为主元，X 是区间里第 k 小的元素，对整个数组进行划分。划分后，数组被分为低区（元素小于 x）、中区（元素等于 x）和高区（元素大于 x）。
  5. 递归选择：根据 i 的值，决定是在低区、中区还是高区递归调用 SELECT 算法：
    • 如果 i 等于 k（x 在数组中的位置），则返回 x。
    • 如果 i 小于 k，则在低区递归调用 SELECT。
    • 如果 i 大于 k，则在高区递归调用 SELECT，且 i = i-k。

图片

我们下面分析该算法的运行时间，证明：其在最坏情况下，运行时间仍为 **O(n)**。

证明