问题标签 [time-complexity]

我编写了一个使用 Prim 方法解决 MST 的代码。我读到这种实现（使用优先级队列）应该有 O(E + VlogV) = O(VlogV) 其中 E 是边数和 V 边数但是当我查看我的代码时它根本不那样。如果有人能为我解决这个问题，我将不胜感激。

对我来说，运行时间似乎是这样的：

while 循环需要 O(E) 次（直到我们遍历所有边） 在该循环中，我们从 Q 中提取一个元素，这需要 O(logE) 时间。第二个内部循环需要 O(V) 时间（尽管我们不是每次都运行这个循环，很明显它会运行 V 次，因为我们必须添加所有顶点）

我的结论是运行时间为：O( E(logE+V) ) = O( E*V )。

这是我的代码：

我有一个场景，我将更改列表推送到另一个系统。每个列表包含零个或多个插入、更新或删除的通知。

插入很容易；通知包含目标索引和指向项目的指针。更新很容易；我传递了一个指向该项目的指针。

删除似乎很简单；我需要传递要删除的项目的索引，但我怎么知道索引？索引从零开始并且必须是连续的，但我在插入时将它们组成。所以我需要跟踪我为每个项目组成的索引。

例如，我可以使用 map: 来做到这一点std::map<item*, int>，但是当我删除一个项目时，我必须重新编号它之后的所有内容，即 O(N)。

这些项目列表将大到不能接受 O(N) 迭代的程度。我确定这个问题已经解决了，我只是不知道解决方案会被称为什么。搜索与“链表”相关的任何内容都会产生大量噪音。

一种可能的解决方案是跳过列表，其中子列表中的每个节点都知道它跳过了主列表中的多少节点，并且由于搜索跳过列表是 O(log N)，我们可以随时跟踪并找到索引O(log N) 并删除 O(log N) 中的项目。

然而，在这里实现一个跳过列表似乎有点过头了......有没有更简单的解决方案？

编辑：

谢谢大家的建议，但我想我已经说服自己跳过列表是解决这个问题的正确方法。

证明算法的上限或下限是什么意思？

我有大量对象，我需要找出它们之间的相似之处。

确切地说：给定两个对象，我可以将它们的相异度计算为一个数字，一个度量- 更高的值意味着更少的相似性，0 意味着对象具有相同的内容。计算这个数字的成本与较小对象的大小成正比（每个对象都有给定的大小）。

在给定一个对象的情况下，我需要能够快速找到与其相似的一组对象。

确切地说：我需要生成一个数据结构，将任何对象 o 映射到与 o 不比 d 更相似的对象集合，对于某些相异值 d，这样列出集合中的对象所花费的时间不会比如果它们在数组或链表中（也许它们实际上是）。通常，该集合将比对象的总数小得多，因此执行此计算非常值得。如果数据结构假设一个固定的 d 就足够了，但如果它适用于任意的 d，那就更好了。

你以前见过这个问题，或者类似的东西吗？什么是好的解决方案？

确切地说：一个简单的解决方案涉及计算所有对象对之间的差异，但这很慢 - O(n ² )，其中 n 是对象的数量。有没有复杂度较低的通用解决方案？

为什么基于比较的排序算法的时间复杂度下限为 O(n log n)？

为什么双向链表中节点删除的时间复杂度（O(1)）比单链表中节点删除时间复杂度（O(n)）快？

我正在学习算法分析。我无法理解 O、Ω 和 Θ 之间的区别。

它们的定义方式如下：

• f(n) = O(g(n))均值c · g(n)是 的上界f(n)。因此，存在一些常数c，对于足够大 （即，对于某个常数） ，f(n)总是 ≤ 。c · g(n)nn ≥ n0n0
• f(n) = Ω(g(n))均值c · g(n)是 的下界f(n)。因此，存在一些常数，对于所有c，f(n)总是 ≥ 。c · g(n)n ≥ n0
• f(n) = Θ(g(n))对于 all 来说，meansc1 · g(n)是 的上界f(n)，c2 · g(n)也是 的下界。因此存在常数和 这样的和。这意味着 对.f(n)n ≥ n0c1c2f(n) ≤ c1 ·g(n)f(n) ≥ c2 ·g(n)g(n)f(n)

我理解的方式是：

• O(f(n))给出给定函数/算法的最坏情况复杂度。
• Ω(f(n))给出给定函数/算法的最佳情况复杂度。
• Θ(f(n))给出给定函数/算法的平均案例复杂度.

如果我错了，请纠正我。如果是这种情况，每个算法的时间复杂度必须用所有三种符号表示。但我观察到它表示为 O、Ω 或 Θ；为什么不是全部三个？

建议解决游戏 Globs 的算法和数据结构 ( http://www.deadwhale.com/play.php?game=131 )。它以一种极客的方式非常有趣。

用 N 表示您的方法的时空复杂度 (big-O)，即网格的大小 (N>=14)。具有低复杂性的足够好的有效算法是首选。

（MatrixFrog 正确地指出这个游戏也被称为 FloodIt，并且 Smashery 在 3 个月前在他引用的链接中给出了一个解决方案。你们所有的家伙都建议修剪/贪婪只有 1 个前瞻，这给出了次优的解决方案。）

游戏生成一个由 nxn 个节点组成的随机方形网格，其中每个节点的颜色为六种颜色之一（Grn=1、Ylw=2、Red=3、Blu=4、Pur=5、Orn=6）。级别 1 有 9x9 网格，然后每个级别增加 n，最多 14 个。每个级别您最多可以进行 25 回合，否则您将失败。在每一回合中，您选择将左上角节点更改为例如 Grn->Red 的颜色，这样新颜色的任何连接的相邻（水平/垂直）节点都被同化为一个形状，并且每个同化节点增加 1 pt你的分数。计分目标是在尽可能少的回合内完成每个网格，例如，如果您在 16 回合内完成，那么您的 9 个未使用的动作 => 2*9 乘以您的总得分。

显然有很多方法可以分解它，默认选择 14x14 网格的递归回溯是一个可行的竞争者；这适用于哪些其他类型的数据结构？一种* ？不要挂在最优性上，我想知道是否有一个“足够好”的算法。

（我认为编写一个机器人并获得愚蠢的高分可能是一个有趣的项目。虽然我的肉件自己获得了 3.5E+12。）

如果我有一个算法需要 4n^2 + 7n 个动作来完成，它的 O 是多少？O(4n^2)? O(n^2)?

我知道 7n 被截断了，但我不知道我是否应该保留 n^2 系数。

谢谢

设置（MySQL）：

这是我上一篇文章的 BFS 解决方案：

挑战，如何实现六度分离的算法？

但它的复杂性是什么？假设完全有n记录。