algorithm - 使用最坏情况、平均情况或摊销分析的惯例？

Question

我了解对算法进行复杂性分析的不同情况的机制，但已经给出了一些场景，并被问及我将对每种情况使用哪种类型的分析。

分析类型为“最坏情况”、“平均情况”、“摊销”。

当然要确保算法尽可能高效，我们总是会选择使用“最坏情况”？

我知道这是主观的，但使用每种分析方法肯定都有优点吗？

这是我在最近的一次工作面试中遇到的 4 种情况，除了关于飞行员的情况外，我无法决定其中的任何一种。

A company has invented a new web search engine and wishes to analyse how quickly how quickly it returns results for a set of common search queries.

A pilot is flying a plane and his inputs on the control stick are converted into wing surface ovements by calculations made in software. The stability of the plane depends on fast responses; we want to analyse if the plane is safe.

A database is sorted the first time a query is made, if previously unsorted. We want to analyse how long a number of consecutive queries would take to perform using this database system.

A cloud computing company hosting an algorithm for weather forecasting and needs to guarantee to compute the next national daily forecast from pressure and other observations data in under 4 hours.

Answer 1

对于实时系统，您需要最坏情况下的复杂性；涵盖您的飞机安全和有保障的国家预报。

在许多应用程序中，您可能需要摊销和平均案例分析(前提是您知道“平均案例”分布)，甚至需要平滑分析以及最坏情况。在某些系统中，“最佳”算法的选择取决于您谈论的是“最差”还是“平均”，有时它们会并行运行多个算法，无论哪种算法完成得更快，都会中止其他算法并输出。