问题标签 [little-o]

正如我在网上搜索的那样，由于计算时间长，我找不到在实践中无法解决的算法示例。

我试图想一个例子，比如计算每颗恒星的数量、大小和位置，这些恒星在前往半人马座阿尔法星的过程中最靠近火箭飞船。这会是一个很好的例子吗？我的意思是，恒星系统距离我们近 26 万亿英里。

编辑：我正在做一个关于 Big-O 和 Little-O 表示法的简短介绍，并想思考一些不同寻常的东西，为什么问题的解决方案可以在实践中解决，但原则上它们可能无法解决，因为计算的时间非常长，因此使用 Big-O 来创建估计。我想和星星一起去的原因是因为它看起来比其他一些主题更有趣。

谢谢！

假设函数 f: R -> R 定义为 f(x) = mx + c 对于 R 中的一些 m, c > 0 和 x。 f(x) 是否属于 o(x)？

如果答案是“否”，我们是否可以得出结论 o(x) 没有正确包含子线性函数集？

我问这个的原因：很容易看出 f(x) 是次线性的，因为 f(x1) + f(x2) = mx1 + c + mx2 + c > m(x1+x2) + c = f(x1+x2)。但是 lim x-> infinity f(x)/x = 2。在这个意义上，f(x) 不在 o(x) 中。但是 o(x) 表示子线性函数的集合。这就是我的困惑的来源。

问题是要证明以下是对还是错。

f(n) = Θ(g(n)) => f(n) = cg(n) + o(g(n)), 对于一些实常数c > 0。

注意：o 很小哦

我试图做以下事情： o(g(n))意味着<cg(n)，对于一些常数c

因此，cg(n) + cg(n) = 2cg(n) = cg(n)这不是渐近紧界

所以R.H.S.是cg(n)<f(n)<cg(n)，L.H.S.而是cg(n)<= f(n) <= cg(n) ，所以声明是错误的

这是合法的吗？

如果f(n) = Θ(g(n))那时我知道f(n)=O(n)和f(n) = Ω(g(n))，那么我会说应该存在 c1 和 c2 ≥ 0，n1 ≥ 0，对于所有 n > n1，存在c1*g(n) ≤ f(n) ≤ c2*g(n)。

证明f(n) = c*g(n) + o(g(n))一些 c > 0。我的观点是f(n) ≤ c2*g(n)==> 我们有f(n) < c2*g(n) + c*g(n) ==> fn ≤ c2*g(n) < (c2 + c)*g(n). 因此，我想说f(n) = c*g(n) + O(g(n))对于某些 c > 0 是正确的。正确吗？

我也可以说f(n) = cg(n) + o(g(n))，对于某些 c > 0？

我有两个功能，f(n),g(n)例如f(n)=o(g(n)).

说清楚，我拿了一点

有了给我的信息，这是可能的f(n)=Omega(g(n))。

对我来说，这听起来不可能，因为 Little-o 定义对我说

谢谢！

假设 f(x) 趋于无穷大，因为 x 趋于无穷大并且 a,b>0。找到产生最低阶的 f(x)

因为 x 趋于无穷大。按顺序我的意思是大 O和小 o符号。

我只能大致解决：

我的解决方案：当 x 趋于无穷时，我们可以说 ln(1+f(x)) 大约等于 ln(f(x))。然后，我必须最小化

因为对于任何 c>0，当 y =sqrt(c) 时，y+c/y 被最小化，所以 b+ln f(x)}=sqrt(ax) 是答案。等效地，f(x)=e^(sqrt(ax)-b) 并且 g(x) 的最低阶是 2 sqrt(ax)。

你能帮我得到一个严格的答案吗？

关于渐近符号的问题。我看过很多关于渐近符号的解释说：

θ(...)类似于=

O(...)类似于<=

o(...)类似于<

这似乎暗示如果f(n) = O(g(n))，那么 要么f(n) = θ(g(n))要么f(n) = o(g(n))。

是否有可能f(n) = O(g(n))既没有f(n) = θ(g(n))也没有f(n) = o(g(n))？如果是这样，这有什么例子？如果不是，那我们为什么要使用O(...)whenθ(...)或o(...)are 更强的描述符？

little-o 是严格上限还是严格上限？

如果有错误，请更正下面的答案，

g(x)是一个f(x)不是渐近紧的上界。if的增长率之间的差距比 iff and g大得多。f ∈ o(g)f ∈ O(g)

Big-O 对 little-o 就像 ≤ 对 <。big-O 是一个包容性的上界，而 little-o 是一个严格的上界。

保证严格的上限还不够吗？

我刚从一家公司得到这个进行面试测试，我轻松完成了它，但他们说我的职能在 o(n) 中。这是问题

使用这些方法编写一个类 IntegerTracker：

确保包括跟踪在内的每个方法都以恒定时间运行（O(1) 时间复杂度）。

我就是这样完成的

有人可以告诉我我应该如何在 O(1) 中完成这个。我已经为此放弃了，所以不要以为你给我面试的答案。我不打算在那里工作。我只想看看我应该如何在不遍历数组的情况下解决这个问题。

我正在寻找一个简单的示例函数 f(n)，它是其他函数 g(n) 的 Big-O，但不是 g(n) 的 Little-o。换句话说，一些 f(n) 使得 f(n) 为 O(g(n))，但不是 o(g(n))。

我能想到的最简单的情况是 f(n) = n, g(n) = n。f(n) 显然是 O(g(n))。我们在课堂上了解到 little-o 符号的一个定义是 f(n)/g(n) as n --> infinity 是否为 0。在这种情况下，f(n)/g(n) as n到无穷大接近 1，因此 f(n)不是o(g(n))。

这个逻辑正确吗？我错过了什么吗？