论文标题
分布分析
Distributional Analysis
论文作者
论文摘要
在分布或平均案例分析中，目标是针对特定概率分布设计具有优质性能的算法。分布分析可用于研究“非病理”输入的通用算法，以及在对相关输入分布有详细了解的应用中设计专业算法的设计。但是，对于某些问题，纯分布分析鼓励对特定分布假设的“过度拟合”算法解决方案，并要求使用更健壮的分析框架。本章列出了分配分析的优缺点的众多示例，强调了其一些最大的热门单曲，同时还为后来的章节中研究的最差和平均案例分析的混合体奠定了基础。
In distributional or average-case analysis, the goal is to design an algorithm with good-on-average performance with respect to a specific probability distribution. Distributional analysis can be useful for the study of general-purpose algorithms on "non-pathological" inputs, and for the design of specialized algorithms in applications in which there is detailed understanding of the relevant input distribution. For some problems, however, pure distributional analysis encourages "overfitting" an algorithmic solution to a particular distributional assumption and a more robust analysis framework is called for. This chapter presents numerous examples of the pros and cons of distributional analysis, highlighting some of its greatest hits while also setting the stage for the hybrids of worst- and average-case analysis studied in later chapters.
