问题标签 [complexity-theory]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
data-structures - 使用 VList 的哈希表
Phil Bagwell 在他2002 年关于 VList 数据结构的论文中指出,您可以使用 VList 来实现持久哈希表。然而,他对它如何工作的解释并没有包含太多细节,我也不明白。谁能给我更详细的解释,甚至是例子?
此外,在我看来,这种数据结构虽然可能具有与 Hashtable 相同的 big-O 复杂性,但会更慢,因为它会进行额外的查找。是否有人愿意详细分析慢了多少,最好包括缓存行为?在没有碰撞或碰撞很多的情况下,两者的性能关系如何变化?
algorithm - 作为流操作的数基转换
有没有办法在恒定工作空间中进行任意大小和任意基本转换。也就是说,要使用 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
最小公倍数在哪里)
complexity-theory - 您创建或看到的最复杂的网站/网页是什么?
您创建或看到的最复杂/最复杂的网站或网页是什么?
是什么让它如此复杂或复杂?
algorithm - 假设 P=NP 证明会是什么样子?
它是针对特定 NP 完全问题的多项式时间算法,还是只是证明存在 NP 完全问题解决方案的抽象推理?
似乎特定的算法更有帮助。有了它,我们要多项式解决一个 NP 问题,我们要做的就是将其转换为证明有解决方案的特定 NP 完全问题,我们就完成了。
theory - 是否有任何 O(1/n) 算法?
是否有任何 O(1/n) 算法?
或者其他任何小于 O(1) 的东西?
heap - 比 O(logn) 增加键更好的最小堆?
我正在使用一个优先级队列,它最初将其元素的优先级基于启发式。随着元素出列,启发式方法会更新,并且当前队列中的元素可能会增加其键。
我知道有些堆(特别是斐波那契堆)已经摊销了 O(1) 减少键操作,但是是否有任何堆结构在增加键操作上有类似的界限?
对于我的应用程序,这远非性能问题(二进制堆工作正常),这实际上只是学术好奇心。
编辑:澄清一下,我正在寻找一种数据结构,其增加键操作的时间比 O(logn) 快,而不是减少键。我的应用程序从不减少密钥,因为启发式高估了优先级。
language-agnostic - O(N log N) 复杂度 - 类似于线性?
所以我想我会因为问这么一个微不足道的问题而被埋葬,但我对某些事情有点困惑。
我已经在 Java 和 C 中实现了快速排序,并且正在做一些基本的比较。该图显示为两条直线,在超过 100,000 个随机整数时,C 比 Java 快 4 毫秒。
我的测试代码可以在这里找到;
我不确定 (n log n) 线会是什么样子,但我认为它不会是直的。我只是想检查这是否是预期的结果,并且我不应该尝试在我的代码中找到错误。
我将公式粘贴到 excel 中,对于以 10 为底的公式,它似乎是一条直线,开始时有一个扭结。这是因为 log(n) 和 log(n+1) 之间的差异线性增加吗?
谢谢,
加夫
sql - 在 mySQL 中压缩 SQL
如何在 MySQL 中简化此代码?
这样计算的日期数是动态的吗?
python - python列表函数的运行时复杂度是多少?
我正在编写一个看起来像这样的python函数
所以它被称为
我曾假设列表的索引访问是O(1)
,但惊讶地发现对于大型列表,这比我预期的要慢得多。
那么,我的问题是如何实现 python 列表,以及以下的运行时复杂性是多少
- 索引:
list[x]
- 从最后弹出:
list.pop()
- 从头弹出:
list.pop(0)
- 扩展列表:
list.append(x)
为了额外的信用,拼接或任意弹出。
c++ - 我在哪里可以找到不同 STL 容器复杂性(性能)的比较?
我用谷歌搜索了很长时间,以便找出一个比较,显示所有 STL 容器在插入/推送擦除/弹出等方面的复杂性差异。我没有找到任何东西。也不是在我所有的 STL 书籍中。有什么提示吗?
我当然知道一些经验法则。但是定义在哪里?