“次线性”是否仍然是一条直线？

Question

我正在研究一个需要“次线性”解决方案的问题。

快速搜索次线性会得到很多这些.

..。其中，次线性线被建模为对数/asymptotic。

但我已经明白了，次线性是任何低于线性基线的东西，因为两者都趋向于无穷大。在这个情节里..。

..。次线性结果仍然是“线性的”(即y = mx + b)，但低于线性基线。

那是哪一种？它必须是渐近/对数的吗？还是倾向于远离线性基线解？

Answer 1

不，不可能。它看起来可以从这个图中得到，因为它是一个日志图，这意味着x和y轴都被压缩了。满足某些常数a和c的关系y= a*x^c的任何函数在日志图中都将显示为一条直线。所以简单的答案是“次线性”情况不是一条直线。

从传说中也可以看出这一点。次线性情形标号为O(N^0.78).在日志图中，这将显示为一条斜率为0.78的直线.然而，与规则地块中的直线相比，它看起来是这样的：

要弄清楚，它不需要像你在问题中问的那样是对数的。在渐近情况下，任何比直线慢的曲线都是次线性的.对数曲线只是一个例子。