Average-case

释义 Definition

average-case：指在平均/期望意义下的情况或表现，常用于计算机科学中描述算法在“典型输入”或按某种概率分布抽样的输入下的平均运行时间/空间开销（区别于最坏情况 worst-case 与最好情况 best-case）。

发音 Pronunciation (IPA)

/ˈævərɪdʒ keɪs/

例句 Examples

The average-case running time is much better than the worst-case.
平均情况下的运行时间比最坏情况好得多。

Although the algorithm has a poor worst-case, its average-case complexity is linear under a random input distribution.
尽管该算法的最坏情况很差，但在随机输入分布下，它的平均情况复杂度是线性的。

词源 Etymology

average 源自中古法语 avarie（与“损坏、分摊损失”有关，后来引申为“按份额分摊→取平均值”），case 来自拉丁语 casus（“发生的事、情形”）。组合成 average-case，字面即“平均情形”，在算法分析里进一步固定为“期望意义下的情形/复杂度”。

相关词 Related Words

• Amortized
• Best-Case
• Big-O
• Complexity
• Expected
• Probabilistic
• Worst-Case

文学与经典作品 Literary Works

• Introduction to Algorithms（CLRS）——在排序、哈希、随机化算法等章节中反复讨论 average-case 与 expected 性能的区别与联系。
• The Art of Computer Programming（Donald E. Knuth）——大量篇幅涉及对算法的平均情况分析（average-case analysis）。
• Algorithms（Robert Sedgewick & Kevin Wayne）——在基础算法与数据结构的性能讨论中频繁使用 average-case。