问题标签 [little-o]

Big-O表示法O(n)和Little-O表示法有什么区别o(n)？

我坐在这里，在一个关于海量数据集算法的课程中完成这项作业，尽管我对 Big-Oh 非常有信心，但 Little-Oh 符号的使用让我感到困惑。

我不想要任务的解决方案，因此我不会介绍它。相反，我的问题是我如何解释时间复杂度o(log n)？

我从定义中知道，算法 A 的增长速度必须比 o(l​​og n) 慢，但我不确定这是否意味着算法必须在恒定时间内运行，或者它是否仍然允许为log n在某些条件下，例如 c = 1 或者如果它真的是log (n-1)。

假设一个算法的运行时间为O(log n)但实际上进行了两次迭代，因此 c = 2，但2*log n仍然是O(log n)，当我说这不成立时，我说得对吗小哦？

非常感谢任何帮助，如果需要澄清，我将提供作业

请注意，我在这里要求 little-o（请参阅此处的类似问题）-对于 big-o，这显然是错误的-对于 little-o，感觉正确但似乎无法证明...

编辑：很高兴我提出了辩论:) 为简单起见假设 f,g > 0

我试图证明对于任何常数，，k（log^k N = o(N)N 中的小 O）

我对小 o 所知道的只是它遵循以低于T(n) = o(p(n))的T(n)速度增长的形式p(n)。我也不能真正做一个限制和使用L'hopital rule，因为我不知道是f(n)什么g(n)。有人可以帮我开始吗！

big-O我认为理解和little-o符号之间的原则区别。但是谁能告诉我为什么big-O在实践中更受欢迎？

根据此页面：

陈述：f(n) + o(f(n)) = theta(f(n)) 似乎是真的。
其中：o = little-O，theta = 大 t​​heta

这对我来说没有直觉意义。我们知道 o(f(n)) 的渐近增长速度比 f(n) 快。那么它怎么可能是大θ所暗示的f（n）的上限？

这是一个反例：

在我看来，先前链接的 stackexchange 答案中的答案是错误的。具体来说，下面的陈述似乎是把小欧与小欧米茄混淆了。

由于 g(n) 是 o(f(n))，我们知道对于每个 ϵ>0，都有一个 nϵ 使得 |g(n)|<ϵ|f(n)| 每当 n≥nϵ

作为一个家庭作业问题，我需要通过数学证明来决定 5 ⁿ是 little-o、Θ 还是 7 ^{n的 little-ω。}然后我需要在取双方的对数后重复这个。

我很难理解我被要求做什么。我最好的猜测是说 A(n) = 5 ⁿ和 B(n) = 7 ⁿ然后使用 l'Hopital 的规则，但我不确定如何继续。我只是在寻找正确的方向。

谢谢！

n ^b = o(a ⁿ ) (o is little oh) 是什么意思？我刚开始自学我的算法，每次看到这样的表达我都很难解释。在这里，我的理解是对于函数 n ^b，增长率是ⁿ。但这对我来说没有意义，无论是对还是错。

IF 优先级队列有两个操作：insert和broken_min。Wherebroken_min返回第一个或第二个最小项。

这些都不能在 o(logn) 时间内实现。我认为这是因为 insert 使用了 broken_min ，然后必须进行更多检查以查看它是否具有最大值。

这是正确的推理吗？

我遇到了这个问题

基本上我可以开始

但是我该如何解决其余的问题？