【机翻】Linear Time Median Finding

原文链接:https://rcoh.me/posts/linear-time-median-finding/

前言

在列表中查找中位数似乎是一个微不足道的问题,但是在线性时间中这样做却很棘手。 在本文中,我将介绍一种我最喜欢的算法,即中位数中值法,以确定性线性时间查找列表的中位数。 尽管证明该算法在线性时间内运行有点棘手,但本文仅针对具有基本算法分析水平的读者。

O(nlogn)O(nlogn)复杂度的求中位数算法

查找中位数的最直接方法是对列表进行排序,然后按其索引选择中位数。
最快的基于比较的排序是 O(nlogn)O(nlogn)

1
2
3
4
5
6
def nlogn_median(l):
l = sorted(l)
if len(l) % 2 == 1:
return l[len(l) / 2]
else:
return 0.5 * (l[len(l) / 2 - 1] + l[len(l) / 2])

尽管此方法提供了最简单的代码,但肯定不是最快的方法。

平均OnO(n)复杂度的求中位数算法

接下来我们要做的通常是在线性时间内找到中位数,前提是我们运气不错。
该算法称为“快速选择”,由Tony Hoare发明,他还发明了类似名称的quicksort。 这是一种递归算法,可以找到任何元素(不仅是中位数)。

  1. 在列表中选择一个索引index。挑选方式并不重要,但在实践中随机选择一个就可以了。该索引处的元素称为基准元素
  2. 通过第一遍快排,将列表划分成两个:
    1. 元素小于或等于基准元素的列表lesser_els
    2. 元素严格大于基准元素的列表great_els
  3. 我们知道这些组之一包含中位数。假设我们正在寻找第k个元素:
    1. 如果lesser_els中有k个或更多元素,则递归列表lesser_els,搜索第k个元素。
    2. 如果lesser_els中的元素少于k,则递归到Greater_els列表中。而不是搜索k,我们搜索k-len(lesser_els)
      这是在包含11个元素的列表上运行的算法的示例:
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
考虑下面的列表。我们寻找其中的中位数。
l = [9,1,0,2,3,4,6,8,7,10,5]
len(l) == 11, 所以我们正在寻找第六个最小的元素
首先,我们必须选择一个基准元素。我们随机选择基准元素3。 该基准元素的值为2。

根据基准元素进行分区:
[1,0,2], [9,3,4,6,8,7,10,5]
我们寻找第六小元素, 6-len(left) = 3, 所以我们要右数组中的第三小元素

我们现在在下面的数组中寻找第三小的元素:
[9,3,4,6,8,7,10,5]
我们随机选择一个元素作为我们的基准元素。
我们选择元素3,即 l[3]=6

根据基准元素进行分区:
[3,4,5,6] [9,7,10]
我们想要第三个最小的元素,所以我们知道它是 左侧数组中的第3个最小元素

现在,我们正在寻找以下数组中的第3个最小数组:
[3,4,5,6]
我们随机选择一个索引作为我们的基准元素。
我们选择索引1,即l [1] = 4处的值。
根据基准元素进行分区:
[3,4] [5,6]
我们正在寻找索引3的项目,所以我们知道它是
正确数组中的最小数组。

我们现在正在寻找下面数组中的最小元素:
[5,6]

此时,我们可以选择一个较大的基本元素
或基于索引的较小元素。
我们正在寻找最小的一项,即5。
return 5

要使用quickselect查找中位数,我们将quickselect提取为单独的函数。我们的quickselect_median函数将使用正确的索引调用quickselect。

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
import random
def quickselect_median(l, pivot_fn=random.choice):
if len(l) % 2 == 1:
return quickselect(l, len(l) / 2, pivot_fn)
else:
return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
quickselect(l, len(l) / 2, pivot_fn))


def quickselect(l, k, pivot_fn):
"""
Select the kth element in l (0 based)
:param l: List of numerics
:param k: Index
:param pivot_fn: Function to choose a pivot, defaults to random.choice
:return: The kth element of l
"""
if len(l) == 1:
assert k == 0
return l[0]

pivot = pivot_fn(l)

lows = [el for el in l if el < pivot]
highs = [el for el in l if el > pivot]
pivots = [el for el in l if el == pivot]

if k < len(lows):
return quickselect(lows, k, pivot_fn)
elif k < len(lows) + len(pivots):
# We got lucky and guessed the median
return pivots[0]
else:
return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)

平均O(n)O(n)的证明

平均情况下,基准元素会将清单分为2个大小大致相等的片段。因此,每个后续递归都对上一步的数据进行1⁄2的运算。

C=n+n2+n4+n8=2nC = n+ \frac{n}{2} + \frac{n}{4} + \frac{n}{8} =2n

有很多方法可以证明该级数收敛到2n。除了直接在此处复制外,我只会带您转到有关此无限系列的出色Wikipedia文章。
Quickselect可为我们提供线性性能,但仅在一般情况下。如果我们不愿意求平均值,而是想保证我们的算法是线性时间,该怎么办呢?

确定O(n)O(n)复杂度求中位数算法

在上一节中,我介绍了快速选择算法,该算法具有平均OnO(n)性能。 在这种情况下,平均值表示平均而言,算法将以O(n)O(n)运行。 从技术上讲,您可能会非常不幸:在每个步骤中,您都可以选择最大的元素作为枢轴。 每一步只会从列表中删除一个元素,实际上您的性能为O(n2)O(n^2),而不是O(n)O(n)
考虑到这一点,接下来是一种选择基准元素的算法。 我们的目标是选择一个线性时间轴,以在最坏的情况下删除足够的元素,以便在与quickselect一起使用时提供O(n)O(n)性能。 该算法最初是由Blum,Floyd,Pratt,Rivest和Tarjan于1973年开发的。 如果我的教程不满意,他们1973年的论文肯定就足够了。 我没有详细介绍散文中的算法,而是在下面对我的Python实现进行了大量注释:

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
39
40
41
42
def pick_pivot(l):
"""
Pick a good pivot within l, a list of numbers
This algorithm runs in O(n) time.
"""
assert len(l) > 0

# If there are < 5 items, just return the median
if len(l) < 5:
# In this case, we fall back on the first median function we wrote.
# Since we only run this on a list of 5 or fewer items, it doesn't
# depend on the length of the input and can be considered constant
# time.
return nlogn_median(l)

# First, we'll split `l` into groups of 5 items. O(n)
chunks = chunked(l, 5)

# For simplicity, we can drop any chunks that aren't full. O(n)
full_chunks = [chunk for chunk in chunks if len(chunk) == 5]


# Next, we sort each chunk. Each group is a fixed length, so each sort
# takes constant time. Since we have n/5 chunks, this operation
# is also O(n)
sorted_groups = [sorted(chunk) for chunk in full_chunks]

# The median of each chunk is at index 2
medians = [chunk[2] for chunk in sorted_groups]

# It's a bit circular, but I'm about to prove that finding
# the median of a list can be done in provably O(n).
# Finding the median of a list of length n/5 is a subproblem of size n/5
# and this recursive call will be accounted for in our analysis.
# We pass pick_pivot, our current function, as the pivot builder to
# quickselect. O(n)
median_of_medians = quickselect_median(medians, pick_pivot)
return median_of_medians

def chunked(l, chunk_size):
"""Split list `l` it to chunks of `chunk_size` elements."""
return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]
文章作者: EderOdan
文章链接: zaihit.com/2019/11/19/%E3%80%90%E7%BF%BB%E8%AF%91%E3%80%91Linear-Time-Median-Finding/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 丁香树下