当有人不加限制地谈论一个算法的大O时,他们指的是最好的、平均的还是最差的运行情况?关键词是“无条件”。

最佳答案

Big-O技术上是上限,所以需要进行最坏情况分析。
还有Big-OmegaBig-Theta,以及预期的病例(如果使用随机化)、平均值等。通常如果有人没有指定,您可以只执行Big-O,但是如果您能够轻松地提供更多信息,那么您也可以。例如,Big-Theta为您提供了Big-O和其他信息。如果你在上算法课,需要对问题进行分析,那么你会想和你的教授谈谈,看看他们期望什么。更有可能的是,他们希望看到你能找出多少,所以without qualification可能意味着向他们展示你知道的或能找出的东西。
当有疑问时,作为请求进一步澄清信息的人通常情况下,你能找到的信息越多越好。通过进一步分析,您可能会发现算法的优势。
例如,使用linked list非常适合插入O(1)。只要您不需要搜索任何东西,那么在算法中使用它可能是一种理想的数据结构。如果您的算法需要进行大量的搜索,那么alinked list可能不是要与您的算法一起使用的数据结构。

关于algorithm - 当有人无条件谈论算法的Big-O时,他们指的是最佳,平均还是最差的情况?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37925400/

10-11 22:45
查看更多