让我们假设我们有一些数据结构，比如n个条目的数组，为了参数起见，让我们假设数据具有有界数值。
有没有一种方法可以确定数据的轮廓，比如单调上升、下降等，达到合理的程度，也许在检查了数据结构中的k个条目后，确定值为z？
假设我们有一个大小为N的数组，这意味着我们在数组中的每个相邻元素之间有N-1个比较。设M=N-1。M表示关系的数量。阵列顺序不正确的概率是
1/M
如果你选择K关系的子集来确定单调上升或下降，那么确定性的理论概率是
K / M
由于这是两个线性方程，很容易看出，如果你想成为.9肯定的，那么你需要检查大约90%的条目。
这只考虑了你问题中的假设。如果你知道概率分布，那么使用统计数据，你可以随机检查数组的一小部分。
如果你只关心数组的相对顺序（例如，在[0,10]的区间上，大多数1都接近开头。），这完全是另一个问题。与仅仅排序相反，这样做的算法必须具有交换元素的高成本和比较的低成本。否则，编写复杂的算法来处理检查将不会带来性能回报。
需要注意的是，这是理论上的。我假设阵列中没有分布。
更容易的问题是从随机数据中检查遇到这种有序行为的概率。
例如。如果数字是随机排列的，则p＝0.5，第一个数字低于第二个数字（我们稍后将讨论重复的情况）。现在，如果你对k对进行采样，并且在任何情况下第一个数字都低于第二个数字，那么观察到它的概率是2^（-k）。
回到重复，跟踪观察到的重复，并将其考虑在内。例如，如果重复的概率是q，则不观察到重复的概率为（1-q），观察到增加或等于的概率是q+（1-q。