Big-O 代数简化问题

Big-O Algebra Simplification Issue

我已经处理一个问题几个小时了,我需要澄清一下:

我需要(尽可能)简化以下大 O 表达式。对于每一个,我都写下了我认为是正确的答案。我想要解决方案,但如果我不正确,我也会很感激解释。我正在尝试尽可能多地学习大 O 表示法,我认为做这些问题很有帮助。我只是想确保我走在正确的道路上。

a) O(sqrt(n) + log(n)*log(n))

我以为这是 O(n)

b) O(3log2 n + 2log3 n)

我以为这是 O(log3 (n))

c) O(n^3 + 2n^2 +3n + 4)

我以为这是 O(n^3)

感谢您的帮助!

让我们一次过一遍。

O(sqrt(n) + log(n)*log(n)). I thought this was O(n)

你是对的,这是 O(n),但这不是一个特别严格的界限。让我们从一个简化的问题开始:O(sqrt(n)) 或 O(log(n) * log(n)) 哪个增长更快?使用该信息,您能否从求和中删除两项中的一项?

O(3log2 n + 2log3 n). I thought this was O(log3 (n))

记住 "big-O ignores the base of logarithms"(即 logb n = O(logc n)对于任何 b 和c 大于一)。你在技术上是正确的,它是 O(log3 n),但这不是最干净的解决方案。你最好在这里说 O(log n)。

O(n^3 + 2n^2 +3n + 4). I thought this was O(n^3)

完全正确!这是可行的,因为 2n2 + 3n + 4 是 O(n3),因此您可以从求和中删除这些项。现在,您可以使用类似的技巧来简化您对 (a) 部分的回答吗?

希望对您有所帮助!

(a) 是我认为最难的一个; (b) 和 (c) 使用相当通用的大 O 简化规则。

对于 (a),我建议做一个替换:让 m = [n 的某个函数使两个项中的一个更简单] 并重新排列得到 n = [something]。然后,您可以使用它来将 m 代入表达式,从而摆脱 n 的所有出现,并根据 Big-Oh 规则对其进行简化。然后,如果你选择的函数是 n 的增函数,你可以将 n 代回,并在需要时进一步简化。

好吧,答案很长,但我从头到尾都很漂亮。

简介: 您需要做的第一件事是正确定义大 O 的含义。Relevant read。传统上它仅被定义为上限。但它在计算机科学中并不是很有用,至少对于像你这样的任务来说是这样。从技术上讲,您可以用比示例增长更快的任何内容来回答,即对所有问题说 O(n!) 在技术上是可以的。

更有用的是big theta,通常在CS中我看到big O被重新定义为big Theta的意思是上面的阅读。不同的是,你的绑定,必须更紧,也从下面申请。

Definitions/Rules: 我最喜欢的计算 Big O(和 Theta)的方法是使用极限。它允许以简单直接的方式对渐近行为关系求和。

基本上如果(x->inf 隐含在这里和之后):

  1. lim f(x) / g(x) = infinity - f 逐渐大于 g
  2. lim f(x) / g(x) is a constant > 0 - f 渐近增长与 g
  3. 相同
  4. lim f(x) / g(x) = 0 - f 渐近增长慢于 g

2 号是大 Theta。数字 2. 和 3. 组合是传统的大 O,如“f 属于 O(g)”(或“is O(g)”令人困惑的措辞)。这意味着 f 不会超过 g 所以 g 是它的上限。

现在用一点数学就很容易证明 Big O(或 Theta)将只关心增长最快的项。这直接来自限制属性。

从现在开始我将使用 O 作为 big Theta,因为它更宽松,所以一切都适用于 Big O。

实例说明: 你的第三个例子是最简单的。您可以安全地删除 2n^2 +3n + 4,因为 n^3 增长得更快。你可以通过计算 lim n^3 / (n^3 + 2n^2 +3n + 4).

来证明 n^3 + 2n^2 +3n + 4O(n^3)

你的第二个例子也是如此,但你需要通过对数属性。基本上:

log b1 (x) = c log b2 (x) - 这意味着您可以以常数为代价来切换对数的底数...并且从上面的规则定义来看,常数因子不会改变任何东西,它仍然是 2。只是不断变化.

你的第一个例子是hardest/trickiest,因为极限是最复杂的。然而,O(f+g) 要么是O(f)要么是O(g),因为其中一个增长得更快,所以另一个可以被丢弃或者它们渐近增长相同所以可以选择其中一个(无论如何,他们增长最快的任期都是相同的)。这意味着您需要检查哪个增长更快,您可以通过...计算 lim sqrt(n)/(log(n)*log(n)) 并根据上面的规则进行选择。我认为这需要 d'Hospital 规则。