bigO，你如何计算/近似它？

Question

bigO，你如何计算/近似它？大多数拥有CS学位的人肯定会知道Big O代表什么。它可以帮助我们衡量算法的实际效率（如何），如果你知道你试图解决的问题属于哪个类别，你可以弄清楚是否仍然可以挤出那么少的额外性能。1但我很好奇，你如何计算或近似算法的复杂性？

Answer 1

小提示：big O符号用于表示渐近复杂度（即，当问题的大小增长到无穷大时），并且它隐藏了一个常量。

这意味着在O（n）中的算法和O（n ²）中的算法之间，最快的并不总是第一个（尽管总是存在n的值，使得对于大小> n的问题，第一个算法是最快的）。

请注意，隐藏常量很大程度上取决于实现！

此外，在某些情况下，运行时不是输入大小 n的确定性函数。例如，使用快速排序进行排序：对n个元素的数组进行排序所需的时间不是常量，而是取决于数组的起始配置。

有不同的时间复杂性：

• 最坏的情况（通常最简单的解决，但并不总是非常有意义）

• 平均情况（通常更难以弄清楚...）

• ...

一个很好的介绍是R. Sedgewick和P. Flajolet 的算法分析导论。

正如您所说，premature optimisation is the root of all evil并且（如果可能的话）在优化代码时应始终使用分析。它甚至可以帮助您确定算法的复杂性。