问题标签 [complexity-theory]

Phil Bagwell 在他2002 年关于 VList 数据结构的论文中指出，您可以使用 VList 来实现持久哈希表。然而，他对它如何工作的解释并没有包含太多细节，我也不明白。谁能给我更详细的解释，甚至是例子？

此外，在我看来，这种数据结构虽然可能具有与 Hashtable 相同的 big-O 复杂性，但会更慢，因为它会进行额外的查找。是否有人愿意详细分析慢了多少，最好包括缓存行为？在没有碰撞或碰撞很多的情况下，两者的性能关系如何变化？

有没有办法在恒定工作空间中进行任意大小和任意基本转换。也就是说，要使用 1 对 1 映射（最好但不一定）保留字典顺序并给出顺序结果，将范围内的n数字序列转换为范围内[1,m]的ceiling(n*log(m)/log(p))数字序列？[1,p]

我对作为管道功能可行的解决方案特别感兴趣，ei 能够处理比存储在 RAM 中更大的数据集。

我发现了许多需要与输入大小成比例的“工作空间”的解决方案，但还没有一个解决方案可以摆脱恒定的“工作空间”。

放弃顺序约束有什么不同吗？即：允许按字典顺序输入导致非按字典顺序输出：

一些想法：

这可能有用吗？

streamBase _n -> convert( n, lcm(n,p)) -> convert( lcm(n,p), p) -> streamBase _p

（lcm最小公倍数在哪里）

您创建或看到的最复杂/最复杂的网站或网页是什么？

是什么让它如此复杂或复杂？

它是针对特定 NP 完全问题的多项式时间算法，还是只是证明存在 NP 完全问题解决方案的抽象推理？

似乎特定的算法更有帮助。有了它，我们要多项式解决一个 NP 问题，我们要做的就是将其转换为证明有解决方案的特定 NP 完全问题，我们就完成了。

是否有任何 O(1/n) 算法？

或者其他任何小于 O(1) 的东西？

我正在使用一个优先级队列，它最初将其元素的优先级基于启发式。随着元素出列，启发式方法会更新，并且当前队列中的元素可能会增加其键。

我知道有些堆（特别是斐波那契堆）已经摊销了 O(1) 减少键操作，但是是否有任何堆结构在增加键操作上有类似的界限？

对于我的应用程序，这远非性能问题（二进制堆工作正常），这实际上只是学术好奇心。

编辑：澄清一下，我正在寻找一种数据结构，其增加键操作的时间比 O(logn) 快，而不是减少键。我的应用程序从不减少密钥，因为启发式高估了优先级。

所以我想我会因为问这么一个微不足道的问题而被埋葬，但我对某些事情有点困惑。

我已经在 J​​ava 和 C 中实现了快速排序，并且正在做一些基本的比较。该图显示为两条直线，在超过 100,000 个随机整数时，C 比 Java 快 4 毫秒。

我的测试代码可以在这里找到；

安卓基准

我不确定 (n log n) 线会是什么样子，但我认为它不会是直的。我只是想检查这是否是预期的结果，并且我不应该尝试在我的代码中找到错误。

我将公式粘贴到 excel 中，对于以 10 为底的公式，它似乎是一条直线，开始时有一个扭结。这是因为 log(n) 和 log(n+1) 之间的差异线性增加吗？

谢谢，

加夫

如何在 MySQL 中简化此代码？

这样计算的日期数是动态的吗？

我正在编写一个看起来像这样的python函数

所以它被称为

我曾假设列表的索引访问是O(1)，但惊讶地发现对于大型列表，这比我预期的要慢得多。

那么，我的问题是如何实现 python 列表，以及以下的运行时复杂性是多少

• 索引：list[x]
• 从最后弹出：list.pop()
• 从头弹出：list.pop(0)
• 扩展列表：list.append(x)

为了额外的信用，拼接或任意弹出。

我用谷歌搜索了很长时间，以便找出一个比较，显示所有 STL 容器在插入/推送擦除/弹出等方面的复杂性差异。我没有找到任何东西。也不是在我所有的 STL 书籍中。有什么提示吗？

我当然知道一些经验法则。但是定义在哪里？