algorithm - 概率空间和预期运行时间：它们是什么？

Question

我遇到了一个问题，我要计算或说明算法的预期运行时间，并说明这种运行时间的概率空间。我会坦率地说我真的不知道我应该做什么。预期运行时间和平均运行时间有什么区别，什么是概率空间，为什么需要它？

Answer 1

他们要求您将算法的运行时间建模为在由该算法的输入集组成的样本空间上定义的随机变量，并计算该随机变量相对于在样本空间上定义的某个概率的期望，作为其值相对于该概率的平均值。

这是一个例子。考虑快速排序。快速排序是一种排序算法，因此将其输入集建模为大小为 N 的排列集是有意义的。因此，样本空间是大小为 N 的排列集。赋予该样本空间以均匀概率，并且然后将运行时间 T_N 定义为随机变量，它将样本空间的元素 s 映射到输入 s 上算法的相应运行时间。然后，T_N 的期望值是其值在样本空间元素上的平均值，即在大小为 N 的排列集上。您可能知道，E[T_N] 为 O(N*log(N)) （E[X] 是随机变量 X 的期望值）。

上一段中唯一需要注意的是，您必须在数学上定义“运行时间”的含义。在实践中，您必须采取算法进行的一些基本操作，例如排序算法中的交换次数或比较次数，并将它们作为精确定义的随机变量来研究。之后，如果您想要为您的计算环境建立一个预测模型，您需要测量您的系统执行每个此类基本操作所花费的时间，并将预期运行时间计算为平均基本操作次数乘以该操作在系统中的执行时间，对于您包含在模型中的每个操作（下面是一个示例）。

以Quicksort为例，对比较次数C_N进行了详细研究，其期望E[C_N]约为2*N*ln(N)-0.846*N。交换次数 S_N 也是如此，其期望值约为 0.333*N*ln(N)-1.346*N。这些结果在本文末尾引用的书的第 1 章中得到了证明。

如果您将系统中比较的运行时间测量为 T_c，将交换的运行时间测量为 T_s，那么您对运行时间的预测将为 E[T_N] = T_c * E[C_N] + T_s * E[S_N] . 然后，您可以替换 E[C_N] 和 E[S_N] 的先前表达式，以获得精确的预测公式。

也许您可以从复习离散概率论的基础知识和/或查看算法分析教科书（如 Sedgewick 和 Flajolet “算法分析简介”）中受益。