algorithm - 大 O 的紧界是什么？

Question

当提到大 o 时，什么被认为是紧束缚？

例如在函数中，f(n) = 10c ₇ n^3 + 10c ₄ nlog(n)) // 这个函数用 n 表示操作的次数 //

根据这个例子，大 O 的严格界限是 O(n ³ )。

在这个例子中，为什么 n ³被认为是 Big O 的紧界？紧束缚表现出什么特征？

另外，波浪值是什么？

根据此示例，此函数的波浪号值为 10c ₇ n ³。

我在网上搜索过，但似乎找不到任何有用的东西。我希望有人能解决这个问题。

Answer 1

紧密界限是当您增加 的值时最能捕捉您的函数的整体增长特征的术语n。

换句话说，10c7n^3 + 10c4nlog(n))是O(n^3)因为其中n^3的项对函数的计算时间影响最大​​，随着n的增加。与立方项相比，函数中的所有其他项对计算时间量的影响微乎其微。

您所说的波浪号值似乎只是包含波浪号的术语；即包含 n 的最高幂的项。（“术语”是函数中由 a+或-符号分隔的部分）

Answer 2

术语紧界表示 f(n)/n^3 和 n^3/f(n) 都是有界的。f(n)~10*c7*n^3 表示 f(n)/10*c7*n^3 在 n 十到无穷大时变为 1。