我正在学习算法分析和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 = 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 + 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
是因为它们是Big-O的定义的一部分:
`f(n) = O(g(n))` means that `f(n) <= c.g(n)` for some c and large enough n
通过查找c
和n0
的值,您可以证明某些功能适合此定义,其中c
是您将g
乘以使其大于f
所需的功能。