问题标签 [big-o]

这是O(N)还是O(1)？为什么？

可能重复：
是否有任何 O(1/n) 算法？

您的代码是否有可能是 Big O 小于 O(1)？

这个关于从有限集中获取随机值的问题让我思考......

人们想要从一组 Y 值中检索 X 个唯一值是很常见的。例如，我可能想从一副牌中发一手牌。我想要 5 张卡片，我希望它们都是独一无二的。

现在，我可以天真地做到这一点，随机选择一张卡片 5 次，每次我得到重复的卡片时再试一次，直到我得到 5 张卡片。但是，对于来自大型集合的大量值，这并不是很好。例如，如果我想从一组 1,000,000 中获得 999,999 个值，那么这种方法会变得非常糟糕。

问题是：有多糟糕？我正在找人来解释 O() 值。获得第 x 个数字将需要 y 次尝试......但是有多少？我知道如何计算出任何给定值，但是有没有一种直接的方法可以将其推广到整个系列并获得 O() 值？

（问题不是：“我怎样才能改进它？”因为它相对容易修复，而且我确信它已经在其他地方多次介绍过。）

我使用的伪代码：

根据我的理解：

• 第 1 行：执行V-1次数。
• 第 2 行：所有顶点的度数之和时间......即2E时间

对于第 2 行：第 3 行和第 4 行需要时间，因为我们正在逐一log E添加/删除所有边缘。PQ

所以总计time= V-1+2E.logE=E.log E

但是书上说是这样E.logV，你能解释一下为什么会这样吗？

我有这个方法，isPalindrome()，我试图找出它的时间复杂度，并更有效地重写代码。

现在我知道这段代码会检查字符串的字符以查看它是否与之前的相同，如果相同，则不会更改 bP。

我认为时间复杂度为 O(N + 3)？这是正确的，如果不是，它是什么以及如何计算出来的。

另外为了提高效率，将字符存储在临时字符串中会更好吗？

什么是 SQL 选择的 Big-O，对于具有n行并且我想要返回m结果的表？

Update, or delete, orCreate操作的 Big-O 是什么？

我说的是一般的mysql和sqlite。

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

我开始学习 Big-Oh 符号。

找到给定函数的C 和 N ₀的简单方法是什么？

比如说：

(n+1) ⁵或 n ⁵ +5n ⁴ +10n ² +5n+1

我知道 Big-Oh 的正式定义是：

设 f(n) 和 g(n) 是将非负整数映射到实数的函数。我们说 f(n) 是 O(g(n)) 如果有一个实常数 c > 0 和一个整数常数 N ₀ >= 1 使得 f(n) <= cg(n) 对于每个整数 N > N ₀。

我的问题是，为 c 和 N ₀选择值的好方法是什么？

对于 (n+1) ⁵上面的给定多项式，我必须证明它是 O(n ⁵ )。那么，我应该如何选择我的 c 和 N ₀以便我可以在不猜测的情况下使上述定义为真？

我知道这不是一个严格的编程问题，而是一个计算机科学问题，所以我希望有人能帮助我。

我一直在做我的算法作业，并找出几种算法的 Big-Oh、Big-Omega、Theta 等。我通过找到它们的 C 和 N ₀值来证明它们并且一切顺利。

然而，我遇到了我在系列中的最后两个问题，我正在努力弄清楚如何解决它们（谷歌并没有多大帮助）。

我以前不必弄清楚总和的大哦/欧米茄。

我的最后两个问题是：

• 证明i ²的Σ (i=1 to n)为 O(N ³ )

和

• 证明[log ₂ i]的Σ (i=1 to n)是 Ω(n log n)

我的问题是，我如何证明这一点？

例如，在第一个中，直觉上我看不出 i ²的总和是 O(N ³ )。第二个更让我困惑。有人可以解释如何显示这些总和的 Big-Oh 和 Big-Omega 吗？

我有 3 个功能：f(n)=2n和g(n)=n!log h(n)=n^（(n) log是(n)base 2）。

比较f(n)和g(n)：阶乘函数，g(n)可以近似为（差的上界）。考虑到这一点，是吗？O(nn)g(n)=Ω(f(n))

我将如何比较g(n)andh(n)和f(n)and h(n)？