algorithm - 算法分析 - 匿名函数证明

Question

基于Big-Theta（或Big-O）的定义，我该如何求解/证明这种格式的方程：（An^2+ Θ(n) = Θ(n^B) where A and B are some constants即两边都有一个O（n））。

我知道如何解决/证明 Big-O 和 Big-Omega，但是当涉及匿名函数时，我完全不知道如何找到 c1、c2 和 n。

Big-O 和 Big-Theta 的示例将不胜感激（让我们使用 A=2 和 B=2 作为两个示例）。

Answer 1

请注意，An^2 + Theta(n)当Theta(n^B)且仅当B == 2。
让我们从现在开始假设它。

根据 Big Theta 的定义，我们知道 Theta(n) 也是 O(n)，因此存在 c1 和 N1 使得对于所有 n > N1: An^2 + Theta(n) <= An^2 + c1*n。

我们还知道存在 c2,N2 使得对于所有 n>N2 An^2 + c1*n <= c2*n^2。我们刚刚根据大 O 的定义得到了 -An^2 + Theta(n)位于O(n^2)（使用常数c2和N=max(N1,N2)），对于 Omega(n^2) 类似地显示，并且您已经根据定义显示An^2 + Theta(n)了在中。Theta(n^2)