无法理解教科书中的 particalur Big-O 示例
Can't understand particalur Big-O example in textbook
到目前为止，了解 Big-O 符号及其计算方式就可以了...大多数情况都很容易理解。但是，我刚刚遇到了一个我一生都无法解决的问题。
说明：select 表达式的最佳大 O 表示法。
(n^2 + lg(n))(n-1) / (n + n^2)
答案是O(n)。这一切都很好，但考虑到分子中的 n^3 因素，这如何合理化？ n^3 不是最好的，但我认为 f(n) <= O(g(n)) 之间有一个 "minimum" 基础？
这本书没有解释任何数学内部工作原理，所有内容都被注入到一个可能的解决方案中（取 f(n) 并生成一个 g(n)，它略大于 f(n) ).
有点难过。如果必须的话，疯狂地学习数学或数学参考。
另外，给定一段代码，如何确定每行的时间单位？您如何根据一行代码（或多行代码）确定对数时间？我知道声明和设置一个变量被认为是 1 个时间单位，但是当事情变得糟糕时，我将如何解决？
非严谨答案：
- 分配分子乘积，发现分子为
n^3 + n log(n) - n^2 - log n。
- 我们注意到，对于大
n，分子增长为 n^3，对于大 n，分母增长为 n^2。
- 我们将其解释为
n^{3 - 2} 大 n 或 O(n) 的增长。
如果把这个算法丢进 Wolfram Alpha，you get this generic result:
如果你展开 (FOIL) 它，你会得到（大致）一个三次函数除以一个二次函数。对于 Big-O，常数无关紧要，较大的幂获胜，所以你会得到 something like this:
接下来就是数学归纳法了。整个算法随着 n 的值越来越大而以类似线性的方式增长。它不是 相当 线性，所以我们不能说它有 (n) 的 Big-Omega，但由于摊销的恒定增长率，它确实相当接近 O(n) .
或者，您可以惹恼到处都是数学家并说，"Since this is based on Big-O rules, we can drop the factor of n from the denominator and thus result in O(n) by simple division." 然而，在我看来，重要的是要考虑到这仍然不是 相当 线性。
请注意，这是一个不够严谨的解释，可能会让您的 class 满意，但这为您提供了一些关于其运行时的基于数学的观点。
到目前为止，了解 Big-O 符号及其计算方式就可以了...大多数情况都很容易理解。但是，我刚刚遇到了一个我一生都无法解决的问题。
说明：select 表达式的最佳大 O 表示法。
(n^2 + lg(n))(n-1) / (n + n^2)
答案是O(n)。这一切都很好，但考虑到分子中的 n^3 因素，这如何合理化？ n^3 不是最好的，但我认为 f(n) <= O(g(n)) 之间有一个 "minimum" 基础？
这本书没有解释任何数学内部工作原理，所有内容都被注入到一个可能的解决方案中（取 f(n) 并生成一个 g(n)，它略大于 f(n) ).
有点难过。如果必须的话，疯狂地学习数学或数学参考。
另外，给定一段代码，如何确定每行的时间单位？您如何根据一行代码（或多行代码）确定对数时间？我知道声明和设置一个变量被认为是 1 个时间单位，但是当事情变得糟糕时，我将如何解决？
非严谨答案：
- 分配分子乘积，发现分子为
n^3 + n log(n) - n^2 - log n。 - 我们注意到，对于大
n，分子增长为n^3，对于大n，分母增长为n^2。 - 我们将其解释为
n^{3 - 2}大n或O(n)的增长。
如果把这个算法丢进 Wolfram Alpha，you get this generic result:
如果你展开 (FOIL) 它，你会得到（大致）一个三次函数除以一个二次函数。对于 Big-O，常数无关紧要，较大的幂获胜，所以你会得到 something like this:
接下来就是数学归纳法了。整个算法随着 n 的值越来越大而以类似线性的方式增长。它不是 相当 线性，所以我们不能说它有 (n) 的 Big-Omega，但由于摊销的恒定增长率，它确实相当接近 O(n) .
或者，您可以惹恼到处都是数学家并说，"Since this is based on Big-O rules, we can drop the factor of n from the denominator and thus result in O(n) by simple division." 然而，在我看来，重要的是要考虑到这仍然不是 相当 线性。
请注意，这是一个不够严谨的解释，可能会让您的 class 满意，但这为您提供了一些关于其运行时的基于数学的观点。