问题标签 [big-o]

2^n + 6n^2 + 3n

我想这只是 O(2^n)，使用最高阶项，但是证明这一点的正式方法是什么？

我正在为明天的一次非常重要的面试做准备，但有一件事我遇到了很多麻烦：排序算法和 BigO 效率。

知道什么数字很重要？最佳、最差或平均效率？

有谁知道我在哪里可以找到组织良好的基本数据结构的渐近分析（可能是一张表，但不是必须的）。我想刷新我对数据结构以及搜索和排序算法的理解。所以我正在寻找最好的，平均。和最坏的情况。

如果它包含 STL 就不会受到伤害。

我只是想知道是否有人可以向我解释一下。我想知道如何使用积分或截断绑定方法计算 Theta 函数的估计值。

例如，您将如何计算：

∑<sub>i=1..ni⋅sqrt(i)+1

每当我考虑算法/数据结构时，我倾向于用常量替换 log(N) 部分。哦，我知道 log(N) 会发散——但这在现实世界的应用程序中重要吗？

对于所有实际目的，log(infinity) < 100。

我真的很好奇现实世界中这不成立的例子。

澄清：

• 我理解 O(f(N))
• 我很好奇现实世界的例子，其中渐近行为比实际性能的常数更重要。
• 如果 log(N) 可以替换为常数，则它仍然可以替换为 O(N log N) 中的常数。

这个问题是为了（a）娱乐和（b）收集论据，如果我（再次）陷入关于设计性能的争议。

输入大小为 100 的算法需要 0.5 ms 秒，如果输入大小为 500 且程序为 O(n lg(n))，则运行需要多长时间？

我的书说，当输入大小加倍时，n lg(n) 需要“略多于两倍的时间”。这对我帮助不大。

我一直这样做的方式是求解常数乘数（这本书没有谈到，所以我不知道它是否有效）：

.5ms = c * 100 * lg(100) => c = .000753

所以

.000753 * 500 * lg(500) = 3.37562ms

这是计算运行时间的有效方法吗，有没有更好的方法来计算它？

我需要找到以下片段的大 O 运行时间：

我知道外循环是 O(n) 但我在分析内循环时遇到问题。我认为它是 O(log n)。

我昨天在算法测试中遇到了这个问题，但我无法弄清楚答案。这让我非常抓狂，因为它值 40 分左右。我认为大多数班级都没有正确解决它，因为我在过去 24 小时内没有提出解决方案。

给定一个长度为 n 的任意二进制字符串，如果存在的话，在字符串中找出三个等距的字符串。编写一个算法，在 O(n * log(n)) 时间内解决这个问题。

所以像这样的字符串有三个“均匀间隔”的字符串：11100000、0100100100

编辑：它是一个随机数，所以它应该能够适用于任何数字。我给出的例子是为了说明“均匀分布”的属性。所以 1001011 是一个有效的数字。1、4和7是均匀分布的。

对于二叉搜索树类型的数据结构，我看到大 O 表示法通常记为 O(logn)。在 log 中使用小写的“l”，这是否意味着自然对数所描述的 log 底 e (n)？很抱歉这个简单的问题，但我一直无法区分不同的隐含对数。

当我分析下面代码段的复杂度时，我发现它是O(n/2)。但是在搜索互联网时，我发现它可能是O(n)。我想知道谁是正确的。