algorithm - 什么是阶数符号 f(n)=O(g(n))？

Question

问题 1：在什么情况下O(f(n)) = O(k f(n))最合适的时间复杂度分析形式？

问题 2：从符号的数学定义开始，对于正常O数，如何证明？O(f(n)) = O(k f(n))k

对于第一个问题，我认为这是时间复杂度的平均情况和最坏情况。我对吗？我还应该写什么？

对于第二个问题，我认为我们需要在数学上定义函数。那么答案是否类似于因为乘以常数只对应k于定义中任意常数的值的重新调整O？

score 3 · Accepted Answer

我的观点：对于第一个，我认为这是时间复杂度的平均情况和最坏情况。我对吗？我还写什么？

不！大 O 表示法与平均情况或最坏情况无关。它只是关于一个函数的增长顺序——特别是一个函数相对于另一个函数增长的速度。一个函数f可以是O(n)平均情况，也可以是O(n^2)最坏的情况——这只是意味着函数的行为取决于其输入，因此必须分别考虑这两种情况。

关于问题 2，从问题的措辞对我来说很明显，您需要从 Big O 的数学定义开始。为了完整起见，它是：

正式定义：f(n) = O(g(n)) 表示存在正常数 c 和 k，使得对于所有 n ≥ k，0 ≤ f(n) ≤ cg(n)。对于函数 f，c 和 k 的值必须是固定的，并且不能依赖于 n。

所以，你需要从这个定义出发，写一个数学证明来证明f(n) = O(k(n)). 首先在上面的定义中替换O(g(n))为；O(k*f(n))其余的应该很容易。

score 2 · Accepted Answer

问题 1 有点模糊，但您对问题 2 的回答肯定是欠缺的。问题是“根据 O 符号的数学定义工作”。这意味着您的讲师希望您使用数学定义：

f(x) = O(g(x)) 当且仅当 limit [x -> a+] |f(x)/g(x)| < 无穷大，对于某些

他希望你代入 g(x) = kf(x) 并证明不等式成立。

您发布的一般论点可能会让您获得部分荣誉，但它是推理而不是数学，问题是要求数学。

2 回答 2