一般情况下，本金和已摊销分析的区别 [英] Difference between average case and amortized analysis

问题描述

我读算法平摊分析的文章。下面是一个文本片段。

  

摊销分析之处在于它是类似于平均情况分析   关心的成本平均操作的序列。   但是，一般情况下，分析依赖于概率假设   关于数据结构和操作，以便计算一个   预计算法的运行时间。因此，它的适用性   依赖于有关的概率分布的某些假设   算法的输入。

     

必然的平均情况并不preclude的可能性，一会   得到不吉利，并遇到一个输入，需要更多超预期   时间，即使假设的输入概率分布是   有效的。

我对上面的文字片段的问题是：

1. 在第一个段落，如何平均情况分析，依靠有关数据结构和操作？概率假设我知道平均情况分析，依赖于输入的概率，但到底是什么上面的语句是什么意思？

2. 什么是笔者的意思是在第二段的平均情况下是无效的，即使输入分布是有效的？

谢谢！

解决方案

1. 要获得平均情况下的时间复杂度，你需要对一般情况是什么样的假设。如果输入的是字符串，什么是平均线？难道只长有关系吗？如果是这样，什么是字符串我将获得的平均长度是多少？如果没有，什么是这些字符串的平均字符（S）？难以明确回答这些问题，如果字符串，例如，姓氏。什么是平均姓？

2. 在最有趣的统计样本中，最大值大于平均值。这意味着你的平均情况分析有时候会低估需要一定的投入（这是有问题的）时间/资源。如果你想想看，对于一个对称的PDF，一般情况下，分析应该低估，因为它高估一样多。最坏情况分析，OTOH，只考虑最有问题的情况下（S），因此保证高估。

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. 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?

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

Thanks!

解决方案

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?

2. 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屋！