BigOh与增长率之间是什么关系？

Question

BigOh与增长率之间是什么关系？增长率是BigOh函数'O'的特征吗？

Answer 1

BigOh只是说，增长率不能大于特定功能增长率的常数，它不能显示什么是增长率。

更新

假设f（n）= 2 * f（n-1）+1并且f（1）= 1，意味着f（n）= 2 ⁿ-1，该函数的BigOh可以是：

BigOh（f（n））属于{2 ⁿ，2 ^n-100，2 ^{2 * n}，2 ^{2 n}。 ..}，但不属于{2 ^{n / 2}，n ²，....}] >>

您可以看到像2 ^{2 n}

这样的函数具有非常快的增长速度，但是它显示了2 ⁿ的BigOh。

某些功能是令人难以置信的，没有人找到它们的确切速度，在这种情况下，BigOh的最佳用法之一。

实际上，当您无法确定θ时，找到好的BigOh是一件好事，坦率地说，我的函数（算法）并不比这个函数慢。因此BigOh是有价值的，但又可能与您的功能增长率相去甚远。 BigOh适用于确定性复杂函数的随机化算法。

Answer 2

据我所知，'O'是

Answer 3

正式而言，BigOh与增长率之间的关系为http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition