问题标签 [little-o]

I'm trying to prove that c²ⁿ = o((loglog n)ⁿ) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n approaches infinity, and I can very easily pick some arbitrary integer value for c and show that indeed ((loglog n)ⁿ) grows at a faster rate. But how do I prove this to be true for any constant c?

证明 f(n) = 2010n^2 + 1388n 属于 o(n^3)

Little-O 定义

到目前为止我的工作：这一定是真的：对于所有常量 c>0，存在一个常量 n0>0 使得所有 n>n0 的 0<=2010n^2 + 1388n<=cn^3

通过简化我们得到： c>= 2010/n + 1388/n^2

不知道接下来要做什么才能找到 n0。

假设我们有两个函数 f(n) 和 g(n)。如果我们想检查 f(n) 是否很小哦 o(g(n))，那么执行以下操作是否有效：

那么如果上面的结果为0，是否意味着f（n）是o（g（n））？我们如何检查有限制的大 theta 和小 omega？

我有这三个考试复习题：

1. 如果f(n) = 2n - 3给出两个不同的函数g(n)和h(n)（所以g(n)不等于h(n)）使得f(n) = O(g(n))和f(n) = O(h(n))
2. g'(n)现在对函数和做同样的事情h'(n)，但是这次函数应该是形式 g'(n) = Ɵ(f(n))和f(n) = o(h'(n))
3. 是否有可能用于函数f(n) = O(g(n))和f(n) = Ω(g(n))？

我知道一个函数是O(n)另一个函数，如果它小于或等于另一个函数。所以我认为 1. 可能是g(n) = 2n²-3and h(n) = 2n²-10。

我也知道一个函数是Ɵ(n)另一个函数，如果它基本上等于另一个函数（我们可以忽略常量），o(n)如果它只小于函数，那么对于 2。我认为你可以有g'(n) = 2n-15and h'(n) = 2n。

To 3.: 一个函数可能同时是O(n)andΩ(n)因为O(n)andΩ(n)允许函数与给定函数相同，所以你可以有一个g(n)等于f(n)并满足既是Oand的规则的函数Ω。

有人可以告诉我这是否正确吗？

我的一个同事问我一个问题：集合o(1)（小符号）是空的吗？

我的问题是：是o(1)空集吗？如果没有，是否存在具有o(1)时间复杂度的程序？

提醒一下， Cormen对 little-o 的定义：

如果对于任何正常数，存在一个常数使得对所有人来说 ，f(n)则称函数在 中。o(g(n))c>0n0 > 00 <=f(n) < cg(n)n>= n0

直观地说，if f(n)is in o(g(n))if it is in O(g(n))，但这个界限并不紧密。

我知道 Big-O 定义了上限，而 Big-Omega 定义了下限。我无法在 Google 上找到 Little-o 和 Little-Omega 是否也定义上限/下限的信息。我读到他们有严格的界限，但这是否意味着他们也定义了上限/下限？谢谢你。

我正在自学 CLRS，我已经达到了这一点——我要回答的问题是：

我把它减少到

现在，在这一点上，所有解决方案手册似乎都很少使用哦

=o(lglgn⋅lglgn)

这一步让我有点困惑；我以为我理解的很少——哦，但显然不够好——有人可以在这个特定的背景下框架它吗？接下来的步骤也从

至

这仅仅是L'hopitals规则的应用吗？

所以我从little o 页面得到的是，当您应用 small O 表示法时，我们必须检查一个速率是否比另一个快（small o 关注上限）？

在这种情况下，当我们应用小 o 时：

2^n = o(3^n) 将是错误的，因为 2^n 和 3^n 上限在速度上相等但不少于

2n = o(n^2) 为真，因为 n^2 上限为 2 且 2n 没有上限。

我在正确的轨道上吗？

所以我正在努力证明（或反驳）上述问题。我觉得这是真的，但我不知道如何表现出来。

同样，问题是如果 g(n) 是 o(f(n))，那么 f(n) + g(n) 是 Theta(f(n))

请注意，这是一个little-o，而不是一个 big-o ！！！

到目前为止，我已经设法（轻松地）证明：

g(n) = o(f(n)) -> g(n) < c*f(n)

那么 g(n) + f(n) < (c+1)*f(n) -> (g(n) + f(n)) = O (f(n))

但是，为了展示 Big Omega，我不知道该在那里做什么。

我这样做对吗？

编辑：每个人都提供了很大的帮助，但我只能标记一个。谢谢你。

我了解 Big-O 和 little-o 之间的区别，但是我想知道何时/为什么会在特定情况下（反之亦然）选择 little-o 而不是 big-O。