我遇到了一个问题，我要计算或陈述一个算法的预期运行时间，并陈述这样一个运行时间的概率空间。我会坦率地说我真的不知道我应该做什么。预期运行时间和平均运行时间之间有什么区别，什么是概率空间，为什么需要它？
最佳答案
他们要求您将算法的运行时间建模为定义在样本空间上的随机变量该算法的输入，并根据在样本空间上定义的某些概率计算该随机变量的期望，作为平均值它相对于该概率的值。
这是一个例子。考虑快速排序。快速排序是一种排序算法，因此将其输入集建模为大小为 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 的“算法分析导论”等算法分析教科书中获益。
关于algorithm - 概率空间和预期运行时间 : what are they?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15441865/