big-o - T(n) 转换为 O(n)

Question

我对处理时间复杂度之间的区别T(N)以及O(N)处理时间复杂度时有点困惑。我有三种算法及其各自的T(N)方程，我必须找到最坏情况的时间复杂度O(N)，我不确定它与T(N).

一个例子是：

T(n) = 150⋅N² + 3⋅N + 11⋅log₂(N)

会O()不会只是O(N²)

另外，是否应该始终使用复杂度较低的算法？我感觉答案是否定的，但我不太确定为什么。

Answer 1

O() 是否只是 O(N²)

是的。

对于大 N，N² 项将主导运行时间，因此其他项不再重要。

例如，对于 N=10，在您的示例中，150⋅N² 已经是 15000，而 3⋅N = 30 和 11⋅log₂(N) = 36.5，因此非 N² 项仅占总数的 0.44%脚步。

对于 N=100, 150⋅N² = 1500000, 3⋅N = 300, 11⋅log₂(N) = 73.1，因此非 N² 项仅占总步数的 0.025%。

因此，对于更高的 N，低阶项的相关性会降低。

另外，是否应该始终使用复杂度较低的算法？

不会。因为 Big-O 表示法仅描述 N 变大时的渐近行为，并且不包括任何常数因子开销，因此您通常最好使用开销较低的次优算法。

在你的例子中，如果我有一个替代算法来解决你试图解决的问题，它的运行时间 T'(N) = 10⋅N³，那么对于 N=10，它只需要 10000 步，而你的例子需要 150067 步. 基本上，对于任何 N ≤ 15，T'(N) 算法会更快，而对于任何 N > 15，您的 T(N) 算法会更快。因此，如果您事先知道您不会看到任何 N > 15，那么您最好选择理论上效率较低的算法 T'(N)。

当然，在实践中还有许多其他考虑因素，例如：

• 您可以在库、网络等中重用的算法的可用性。
• 如果你自己实现它：易于实现
• 算法是否容易扩展到多核或多台机器

Answer 2

T(n) 是表示输入大小为 n 所用时间的函数。大哦符号是一种分类。就像您在示例中所说的那样，该示例的大哦将是 n^2。

关于您的第二个问题，大哦符号表示您应该使用的算法，因为输入大小接近无穷大。实际上，在某些情况下，您永远无法获得足够大的输入来进行补偿。

例如，如果 T1(n) = 999999999999*N 且 T2(n) = 2*N^2，最终 n 大到足以使 T2 大于 T1。然而，对于较小尺寸的 n，T1 较大。您可以绘制函数图，甚至求解方程组以找出 n 的大小会产生影响。

注意：还请记住，big-oh 是复杂性的界限，这意味着您可以有一个仍然正确的松散界限。

Answer 3

T(n) 只是一个函数。O 或 big oh 是复杂程度。

就此而言，T(n) 可以是 f(n) 或 g(n)。

我希望这很清楚。

Big Oh 是衡量算法时间或空间复杂度的指标。

您不考虑复杂度的低阶，因为对于非常大的 n 值，高阶复杂度是 >> 低阶复杂度。