是否正确或不正确地说输入表示$ C $导致算法的平均运行时间？

Question

我正在通过cormen等来通过文本介绍算法。 al。我遇到的那个摘录，我觉得需要一些澄清。

现在我所知，当最佳案例和最坏的情况时间复杂地产生算法的某个物理输入（比如说输入 $ a $ 导致算法的最坏情况运行时间或说出输入 $ b $ 导致算法的最佳案例运行时间，渐近地），但没有这样的物理输入，这导致算法的平均案例运行时间随着算法的平均案例运行时间是通过定义算法的运行时间对所有可能的输入进行平均值。这是我希望只在数学上存在。

但另一方面，另一方面，算法既不是最佳案例输入也不是最坏情况输入，应该在极值之间的某个位置和我们的算法的性能之间以除了平均值的方式测量它们作为算法的平均水箱时间复杂度，算法之间的平均案例复杂度就像我们的两个极端之间的输入一样。

是正确或不正确的说，输入 $ c $ 导致算法的平均运行时间？

从文本中摘录，让我提出这样一个问题如下：

在Quicksort分析的背景下，

在平均案例中，分区产生“良好”和“糟糕”分裂的混合。在递归树中，平均执行分区的情况下，良好和坏的拆分在整个树中随机分布。为了直觉，假设良好和坏的分裂树中的替代水平，并且良好的分裂是最佳的分裂，并且坏分裂是最差的分裂。图（a）显示递归树中连续两个级别的拆分。在树的根目录中，成本为 $ n $ 进行分区，并且生成的子阵列具有大小 $ n-1 $ 和 $ 0 $ ：最坏的情况。在下一级别，大小的子阵列 $ n-1 $ 以大小的子阵列进行最佳案例分区 $（n -1）/ 2 - 1 $ 和 $（n-1）/ 2 $ 让我们假设边界条件成本是 $ 1 $ 用于大小的子阵列 $ 0 $ 。

坏拆分后跟良好的拆分的组合产生了三个大小的三个子阵列 $ 0 $ ， $（ n-1）/ 2 - 1 $ 和 $（n-1）/ 2 $ 以 $ \ theta（n）+ \ theta（n-1）=theta（n）$ 。当然，这种情况并不比图（b）更糟糕，即产生两个大小的两个子阵列 $（n-1）/ 2 $ 的单个分区级别，以 $ \ theta（n）$ 的成本为代价。然而，后一种情况是平衡的！

Answer 1

关于一些分发 $ d $ 的算法的平均案例运行时间是按定义，预期的运行时间在根据 $ d $ 的输入上运行时运行算法。

这应该与最坏情况下的运行时间对比，这是给定长度的任何输入的最大运行时间，以及最佳案例运行时间，这是任何给定长度的输入上的最小运行时间。

由于最坏情况和最佳情况运行时间定义为最大值和最小值，因此有输入它们的输入。平均案例运行时间是一个期望，因此毫无意义地谈论实现它们的输入。

如果你扔死，你得到的预期号是3.5。任何特定投掷都没有实现这一点。如果模具有5个边，则预期的数量为3，这确实对应于某些抛光，但这并不意味着投掷是“平均案例”。

---

有时会发生什么样的是，您可以隔离一类输入 $ x $ ，使得当在上运行时运行$ x $ ，算法的运行时间在平均水平运行时间的恒定因子范围内（为此有意义， $ x $ 实际上应该对应于每个长度的输入的序列 $ x_n $ ，或者至少无限多长度）。您可以说 $ x $ “达到”算法的预期运行时间。