大O符号的数据结构

Question

我有关于大O符号 的方程

f(n)=3n+8 

我们怎么找到的上界以及我们如何找到大O表示法无疑 给出的解决方案是

3n+8<=4n和n>8，其中c=4和n_0=8

我不知道这个解决方案是如何发现的。你能解释一下如何解决这个问题吗？从CLRS大哦符号的

Answer 1

数学定义：

O(g(n)) = { f(n) : there exists positive constants c and n_0 such that 0 <= f(n) <= c.g(n) for all n >= n_0 } 

让f(n)=3n+8。

然后，我们必须找到正的常数c和n_0，使得0 <= 3n+8 <= c.g(n) for all n >= n_0。

让g(n)=n。 （如果你愿意，可以试试各种功能）

然后，0 <= 3n+8 <= cn for all n >= n_0。只有当c的值大于3和n值大于或等于8

这个表达式将保持为真。如果情况并非如此，那么这种线性不等式将失败。例如：

• 如果c = 3，那么我们将得到0 <= 3n+8 <= 3n这是错误的。
• 如果c = 4和n_0 = 7，那么我们将得到0 <= 3n+8 <= 4n，这意味着0 <= 3.7+8 <= 4.7，它给出0 <= 29 <= 28，这又是错误的。

因此，我们可以得出结论f(n) = O(n) for c = 4 and n_0 = 8。

This是一个很好的资源，如果你想了解更多。