如果我遍历列表并删除遇到的每个无序元素，平均会留下多少元素？

Question

我有一个均匀随机排列的长度列表 $n$. 。我逐个元素地遍历列表，如果元素无序（与列表中之前的有序元素相比），则将其删除。我剩下的是一个较短的列表，并且保证是有序的。

例子：该列表中加星标的元素将在演练过程中被删除。

[1, 4, 2*, 3*, 5, 7, 6*] -> [1, 4, 5, 7]

我的问题是：平均而言，剩余列表的长度是多少？是否存在某种简单/明显的分布形式？

作为后续行动之一：如果我们将其用于排序算法（称为 Drop Sort），运行时间会是多少？需要明确的是，该算法将是这样的：$$ extit{DropSort}( ext{列表}) = extit{合并}( ext{剩余列表}, extit{DropSort}( ext{拒绝列表}))$$

这个问题的灵感来自于此 r/Programmer幽默帖子.

Answer 1

您可以使用期望的线性来计算平均值。

令随机变量 $X$ 表示保留的元素数量。让 $X_i$ 成为指标 r.v.如果 $i$第一个元素被保留，否则为 0。然后 $X = X_1+\点 + X_n$, ， 所以

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1] .$$

现在 $i$当且仅当第一个元素是第一个元素中最大的数时，该元素才会被保留 $i$ 列表中的元素。所以， $\Pr[X_i=1]=\frac{1}{i}$, ， 所以

$$\mathbb{E}[X] = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \approx \log(n) + \gamma $$

换句话说，剩余列表的平均长度是 $O(\log n)$.

我不知道分布是什么。

作为启发式，Drop Sort 的预期运行时间将满足类似的递归 $T(n) \大约 T(n-\log(n)) + O(n)$, ，对应于 $O\left(\frac{n^2}{\log n} ight)$ 时间。