algorithm - 渐进地比较函数

Question

我有两个函数:F₁(n)=2n+20 和 F₂(n)=n+1。我必须证明哪个更好。

我们的讲师解决了类似的问题。给定 F₁(n)=n² 和 F₂(n)=2n+20，他做了:

F₂(n)/F₁(n)=(2/n)+(20/n²)

他说它总是小于 22，因此 2n+20 更好。

我的疑问是如何解决这些函数之间的比较类型。我已经完成了之前在这里提出的所有问题，但不太明白。

另外如果给定(an²+bn+c)=O(n²)，请帮忙选择常量c₁， c₂, n₀ 这样

c₁g(n) ≤ f(n) ≤ c₂g(n).

Answer 1

正如其中一条评论所述，首先需要定义什么是更好的复杂性。

您的讲师可能意味着复杂性 C(n) 优于 K(n)当且仅当 C(n) << K(n) (或使用朗道符号 C(n) = o(K(n)) )作为 n -> +Inf .

如果要比较两个复杂度F1(n)和 F2(n) , 一种方法是检查商 F2(n)/F1(n)收敛，如果是，收敛到哪个值。与 F2(n) ~ n和 F1(n) ~ n^2 , F2(n)/F1(n)收敛于0因此 F1(n)主宰F2(n)走向无穷大。你会说 F1(n)鉴于较早采用的语言约定更好。

请注意，“它 ( F2(n)/F1(n)) 总是小于 22，并且告诉我们 2n+20 更好”不是渐近分析的正确方法，以防万一支配关系(o(.) 或等效的 << )(我怀疑你的讲师针对上面定义的 F1(n) 和 F2(n) 说过。)。

在你的最后一个问题中 - 你能否定义 f(n)和 g(n) ？