平均案例和摊销分析之间的差异 [英] Difference between average case and amortized analysis

问题描述

我正在阅读一篇关于算法摊销分析的文章.以下是文字片段.

I am reading an article on amortized analysis of algorithms. The following is a text snippet.

摊销分析类似于平均情况分析，因为它是与一系列操作的平均成本有关.然而，平均案例分析依赖于概率假设关于数据结构和操作，以便计算算法的预期运行时间.因此它的适用性是取决于关于概率分布的某些假设算法输入.

Amortized analysis is similar to average-case analysis in that it is concerned with the cost averaged over a sequence of operations. However, average case analysis relies on probabilistic assumptions about the data structures and operations in order to compute an expected running time of an algorithm. Its applicability is therefore dependent on certain assumptions about the probability distribution of algorithm inputs.

平均个案界限并不排除人们将变得不走运"并遇到需要超出预期的输入即使输入概率分布的假设是有效.

An average case bound does not preclude the possibility that one will get "unlucky" and encounter an input that requires more-than-expected time even if the assumptions for probability distribution of inputs are valid.

我对上述文本片段的问题是:

My questions about above text snippet are:

1. 在第一段中，平均情况分析如何依赖于关于数据结构和操作的概率假设?"我知道平均情况分析取决于输入的概率，但上面的陈述是什么意思?

1. In the first paragraph, how does average-case analysis "rely on probabilistic assumptions about data structures and operations?" I know average-case analysis depends on probability of input, but what does the above statement mean?

作者在第二段中的意思是，即使输入分布有效，平均情况也无效?

What does the author mean in the second paragraph that average case is not valid even if the input distribution is valid?

谢谢！

推荐答案

1. 要获得平均情况的时间复杂度，您需要对平均情况"是什么做出假设.如果输入是字符串，那么平均字符串"是什么?只有长度重要吗?如果是这样，我将得到的字符串的平均长度是多少?如果不是，这些字符串中的平均字符是多少?例如，如果字符串是姓氏，则很难明确回答这些问题.平均姓氏是多少?

1. To get the average-case time complexity, you need to make assumptions about what the "average case" is. If inputs are strings, what's the "average string"? Does only length matter? If so, what is the average length of strings I will get? If not, what is the average character(s) in these strings? It becomes difficult to answer these questions definitively if the strings are, for instance, last names. What is the average last name?

在大多数有趣的统计样本中，最大值大于平均值.这意味着您的平均案例分析有时会低估某些输入所需的时间/资源(这是有问题的).如果您考虑一下，对于对称 PDF，平均案例分析应该低估和高估一样多.最坏情况分析 OTOH 只考虑最有问题的情况，因此肯定会高估.

In most interesting statistical samples, the maximum value is greater than the mean. This means that your average case analysis will sometimes underestimate the time/resources needed for certain inputs (which are problematic). If you think about it, for a symmetrical PDF, average case analysis should underestimate as much as it overestimates. Worst case analysis, OTOH, considers only the most problematic case(s), and so is guaranteed to overestimate.

这篇关于平均案例和摊销分析之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！