big-o - Big-O - 函数的增长率

Question

我想了解更多关于Big-O的信息，并找到了以下信息：

'如果f(x) = O(g(x))的增长率f(x)渐近小于或等于g(x)'

在这种情况下渐近意味着什么？我也很难理解为什么 Big-Theta 不依赖于我们使用的计算机？谁能提供有关这两个问题的更多信息？

Answer 1

在此上下文中，术语“渐近地”指的是“随着 x 趋于无穷大”。当有人说“f(x) 渐进地比 g(x) 增长慢”时，他们的意思是对于非常大的 x 值，函数 g(x) 将比函数 f(x) 增长得更快。这意味着对于足够大的 x，只要 f(x) ≥ 1 且 g(x) ≥ 1，g(x) 的值最终总是会大于函数 f(x)。

至于这个问题：

我也很难理解为什么 Big-Theta 不依赖于我们使用的计算机？

尽管 O、Θ 和 Ω 符号在 CS 中广泛用于描述运行时，但这并不是它们的真正含义。从技术上讲，这个符号用于量化函数的增长率，而不管这些函数的实际含义是什么。例如，您会发现斯特林近似中使用的大 O 表示法在离散数学中，估计 ln n! 如 n ln n - n + O(log n)，其中 O(log n) 表示“某个函数的增长率为 O(log n)”。在 CS 中，当我们说一个算法是 O(n) 时，真正的意思是“描述这个函数运行时间的函数是 O(n)”。更准确地说，您会看到诸如“算法的运行时间是 O(n)”或“算法需要时间 O(n)”之类的表达方式，强调使用大 O 表示法来描述算法的运行时间，而不是比算法本身。从这个意义上说，您的问题“为什么 Θ 符号不依赖于计算机？”的一个答案是？是“Θ符号只是量化函数的增长率，与计算机无关。”

在另一种意义上，特定计算机无关紧要的原因是 Θ 表示法谈论的是渐近运行时，而不是绝对运行时。如果一个算法的运行时间为 Θ(n)，这意味着该算法的运行时间可以缩放为某个线性函数。该算法的运行时间作为输入的大小实际上可能是 100n + 137 或 20,000,000n - 15，因为重要的是这些运行时间的增长方式，而不是运行时间本身。如果您在不同的计算机上运行相同的代码，可能会花费更多或更少的时间来运行，具体取决于所选的计算机，但几乎可以肯定它不会从线性缩放变为二次缩放。这意味着渐近地，运行时是相同的，尽管绝对运行时可能非常不同。

希望这可以帮助！