代码之家  ›  专栏  ›  技术社区  ›  Yatendra Rathore

在算法分析期间寻找上界的不同行为是什么?

  •  0
  • Yatendra Rathore  · 技术社区  · 7 年前

    我在学习算法分析和大O符号。有以下练习示例可供参考:

    示例1: 求f(n)=3n+8的上界

    解决方案: 3n+8?4n,适用于所有n 8

           ∴ 3n + 8 = O(n) with c = 4 and n0 = 8
    

    另一个,

    示例2: 求f(n)=n^2+1的上界

    解决方案: n^2+1’2(n^2),对于所有n 1

           ∴ n^2 + 1 = O(n^2) with c = 2 and n0 = 1
    

    接下来是一个让我困扰的例子,

    示例3: 求f(n)=2n^3 2n^2的上界

    解决方案: 2n^3–2n^2–2n^3,对于所有n–1

           ∴ 2n^3 – 2n^2 = O(n^3 ) with c = 2 and n0 = 1
    

    在最后一个例子中,我们为什么使用2n^3进行比较?

    意味着在每个示例中,我们使用了更大的值,即在第一个示例中,我们使用4n,因为方程的最大极限为3n,

    在第二个例子中,我们使用了2(n^2),因为n^2是该方程中的最大值。

    这意味着在第三个等式中,我们应该使用3(n^3)而不是2(n^2)。

    也许我没有得到什么东西,你能详细解释一下缺失的部分吗?

    这里对c和n0的需求是什么。n0是我们考虑给定算法增长率的点,但为什么是c? 我不熟悉算法分析。

    1 回复  |  直到 7 年前
        1
  •  3
  •   fgb    7 年前

    替换这些项,使所有指数相同。对于上限,您希望用更大的值替换它们。增加指数将为正项生成更大的值,但对于负项,则可以将其替换为0,从而删除该项。

    对于 3n + 8 , 3n + n 是一个上限,因为 8 <= n 对于 n > n0 .

    对于 n^2 + 1 , n^2 + n^2 是一个上限,因为 1 <= n^2 对于 n>n0 .

    对于 3n^3 - 2n^2 , 3n^3 + 0 是一个上限,因为 -2n^2 <= 0 对于 n>n0 .


    c n0 因为它们是大O定义的一部分:

    `f(n) = O(g(n))` means that `f(n) <= c.g(n)` for some c and large enough n
    

    通过查找 c n0 ,可以证明某些函数符合此定义,其中 是你需要乘的 g 通过使其大于 f .