Average-case

定义 Definition

average-case（平均情况）：在算法分析或复杂度讨论中，指在某种输入分布假设下，对算法运行时间、空间使用或性能指标取期望值后的表现。常与 worst-case（最坏情况）、best-case（最好情况） 对比；不同分布假设会导致平均情况结果不同。

发音 Pronunciation

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

例句 Examples

The average-case time complexity of this algorithm is O(n log n).
这个算法的平均情况时间复杂度是 O(n log n)。

Although the worst-case can be quadratic, the average-case performance is usually acceptable for typical inputs.
尽管最坏情况可能是二次方级别，但对典型输入而言，它的平均情况性能通常是可以接受的。

词源 Etymology

average 源自中古法语 avarie（与“海损、损失分摊”相关），后来引申为“均摊后的平均值”；case 来自拉丁语 casus（“情形、事件”）。合起来的 average-case 在计算机科学语境中表示“按（假设的）输入情形分布求平均的那种情况/表现”。

相关词 Related Words

• Average
• Worst-Case
• Best-Case
• Expected
• Expectation
• Complexity
• Runtime
• Probabilistic
• Amortized
• Distribution

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常简称 CLRS）：在排序、哈希、随机化算法等章节中讨论 average-case 分析。
• The Art of Computer Programming（Donald E. Knuth）：大量使用平均情况/期望分析来刻画算法性能。
• Randomized Algorithms（Rajeev Motwani, Prabhakar Raghavan）：平均情况与期望性能是核心概念之一。