使用最坏情况、平均情况或摊销分析的惯例？
Convention for using Worst-Case, Average-Case or Amortized Analysis?
我了解对算法进行复杂性分析的不同情况的机制，但已经给出了一些场景，并被问及我将对每种情况使用哪种类型的分析。
分析类型有"worst-case"、"average-case"、"amortized"。
当然要确保算法尽可能高效，我们总是会选择使用 "worst-case"？
我知道这是主观的，但使用每种分析方法肯定都有优点吗？
这是我在最近的一次求职面试中遇到的 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.
软件操作的要求决定了您需要查看算法的哪些特征。换句话说，没有通用的答案。你所说的 "subjective" 更像是 "it depends on the circumstances".
对于实时系统，您需要最坏情况的复杂性；涵盖您的飞机安全和有保障的国家预报。
在许多应用程序中，您可能需要摊销和平均情况分析（前提是您知道 "average case" 分布）或者甚至是最坏情况下的平滑分析。在某些系统中，"best" 算法的选择取决于您谈论的是 "worst" 还是 "average"，有时它们会 运行 多个并行算法，以较快完成的算法中止其他的和输出。
我了解对算法进行复杂性分析的不同情况的机制，但已经给出了一些场景，并被问及我将对每种情况使用哪种类型的分析。
分析类型有"worst-case"、"average-case"、"amortized"。
当然要确保算法尽可能高效，我们总是会选择使用 "worst-case"？
我知道这是主观的，但使用每种分析方法肯定都有优点吗？
这是我在最近的一次求职面试中遇到的 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.
软件操作的要求决定了您需要查看算法的哪些特征。换句话说，没有通用的答案。你所说的 "subjective" 更像是 "it depends on the circumstances".
对于实时系统，您需要最坏情况的复杂性；涵盖您的飞机安全和有保障的国家预报。
在许多应用程序中，您可能需要摊销和平均情况分析（前提是您知道 "average case" 分布）或者甚至是最坏情况下的平滑分析。在某些系统中，"best" 算法的选择取决于您谈论的是 "worst" 还是 "average"，有时它们会 运行 多个并行算法，以较快完成的算法中止其他的和输出。