在算法分析期间找到上限时,采取不同的行为是什么

  • 本文关键字:是什么 算法分析 algorithm big-o
  • 更新时间 :
  • 英文 :


我正在学习算法分析和BIG-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?我是算法分析的新手。

术语被替换,因此所有指数均相同。对于上限,您想用更大的值替换它们。增加指数将产生较大的正值值,但是对于否定术语,您可以用0代替0,删除该术语。

对于3n + 83n + n是上限,因为8 <= n用于n > n0

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

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


cn0是因为它们是Big-O的定义的一部分:

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

通过查找cn0的值,您可以证明某些功能适合此定义,其中c是您将g乘以使其大于f所需的功能。

最新更新