问题标签 [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.

0 投票
2 回答
566 浏览

data-structures - 使用 VList 的哈希表

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

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

0 投票
3 回答
782 浏览

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最小公倍数在哪里)

0 投票
4 回答
11028 浏览

complexity-theory - 您创建或看到的最复杂的网站/网页是什么?

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

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

0 投票
15 回答
5559 浏览

algorithm - 假设 P=NP 证明会是什么样子?

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

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

0 投票
32 回答
67360 浏览

theory - 是否有任何 O(1/n) 算法?

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

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

0 投票
3 回答
3686 浏览

heap - 比 O(logn) 增加键更好的最小堆?

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

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

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

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

0 投票
7 回答
101676 浏览

language-agnostic - O(N log N) 复杂度 - 类似于线性?

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

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

结果

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

安卓基准

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

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

谢谢,

加夫

0 投票
3 回答
677 浏览

sql - 在 mySQL 中压缩 SQL

如何在 MySQL 中简化此代码?

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

0 投票
5 回答
37435 浏览

python - python列表函数的运行时复杂度是多少?

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

所以它被称为

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

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

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

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

0 投票
3 回答
24188 浏览

c++ - 我在哪里可以找到不同 STL 容器复杂性(性能)的比较?

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

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