nonlinear-functions - f(x) = 2*x + 1 是否属于 $o(X)$？

Question

假设函数 f: R -> R 定义为 f(x) = mx + c 对于 R 中的一些 m, c > 0 和 x。 f(x) 是否属于 o(x)？

如果答案是“否”，我们是否可以得出结论 o(x) 没有正确包含子线性函数集？

我问这个的原因：很容易看出 f(x) 是次线性的，因为 f(x1) + f(x2) = mx1 + c + mx2 + c > m(x1+x2) + c = f(x1+x2)。但是 lim x-> infinity f(x)/x = 2。在这个意义上，f(x) 不在 o(x) 中。但是 o(x) 表示子线性函数的集合。这就是我的困惑的来源。

Answer 1

不，f(x) = 2x + 1 ∉ o(x)。

我认为您的困惑来自sublinear的定义。线性代数和计算机科学在这里使用两种不同的含义：

• 在线性代数中，次线性函数是线性函数的推广，即每个线性函数都是次线性函数。正如您在问题中所示，您的 f(x) 满足子可加性标准。

• 在计算机科学中，线性和次线性描述了渐近行为。在给定足够大的输入的情况下，次线性函数是一个比每个线性函数增长得更慢的函数。因此，没有线性函数是次线性函数。

因此，您的 f(x) 是线性代数的次线性，但它不是计算机科学的次线性。