问题标签 [time-complexity]
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.
complexity-theory - 关于独立集问题的NP-完全性问题
我认为,当证明一个问题 P 是 NP-Complete 时,我们应该将一个已知的 NPC 问题简化为 P。但是,看看独立集问题的解决方案,它似乎不是这样。
为了证明独立集是 NP 完全的,你需要一个图 G,找到它的逆 G',然后计算 CLIQUE(G')。但是,这是相反的:它处理一个问题 PI 不知道它是否是 NPC,然后将其简化为已知 NPC 问题。
这是解决方案的一个示例。
我在这里想念什么?这难道不是错的,因为它是反过来做的吗?
java - java ArrayList 的时间复杂度
java中是ArrayList
数组还是列表?get 操作的时间复杂度是多少O(n)
?O(1)
time-complexity - 时间复杂度混淆
我一直对此感到有些困惑,可能是由于我对编译器缺乏了解。但是让我们以 python 为例。如果我们有一些名为 numlist 的大型数字列表,并且想要删除任何重复项,我们可以在列表上使用集合运算符,例如 set(numlist)。作为回报,我们将获得一组数字。据我所知,此操作将在 O(n) 时间内完成。虽然如果我要创建自己的算法来处理这个操作,我所希望的绝对最好的结果是 O(n^2)。
我没有得到的是,是什么允许像 set() 这样的内部操作比语言算法的外部操作快得多。检查仍然需要完成,不是吗?
algorithm - 计算算法复杂度 - 混乱
我有以下代码片段:
复杂性会是O(n^2)
,但如果我想进一步挖掘内部循环的复杂性,那么它会是(n (n-1))/2
还是(n-1)!
?
algorithm - 使用多项式时间的“最难”问题是什么?
最近我读了一篇研讨会的作品,上面写着:
匹配算法[用于一般图]可以扩展到加权情况,这似乎是可以在多项式时间内解决的“最难”的组合优化问题之一。
我立刻想到了以下问题:
你知道其他“P-hard”问题吗?
现在我想将 P-hard 定义为:“在该问题的文献中很晚才(1950 年之后)发现了多项式算法”。(或者如果已经有一种确定性算法可以在多项式时间内解决问题,那么如何更好地定义“困难”?)
algorithm - O(log n) 到底是什么意思?
我正在学习 Big O Notation 运行时间和摊销时间。我理解O(n)线性时间的概念,这意味着输入的大小会成比例地影响算法的增长......例如,二次时间O(n 2 )等也是如此......甚至算法,例如置换生成器,具有O(n!)次,按阶乘增长。
例如,以下函数是O(n),因为算法的增长与其输入n成比例:
类似地,如果有一个嵌套循环,时间将是 O(n 2 )。
但是O(log n)到底是什么?例如,完全二叉树的高度为O(log n)是什么意思?
我确实知道(也许不是很详细)对数是什么,从某种意义上说:log 10 100 = 2,但我不明白如何识别具有对数时间的函数。
algorithm - 不相交集森林数据结构的无秩联合/查找算法
以下是wikipedia上不相交集森林的联合/查找算法的细分:
- 准系统不相交的森林... (
O(n)
)- ...按等级联合...(现在改进为
O(log(n)
)- ... 带有路径压缩(现在改进为
O(a(n))
, 有效O(1)
)
- ... 带有路径压缩(现在改进为
- ...按等级联合...(现在改进为
按等级实现联合需要每个节点保留一个rank
字段以进行比较。我的问题是,按等级联合是否值得这个额外的空间?如果我按等级跳过联合而只进行路径压缩会发生什么?够好吗?现在的摊销复杂度是多少?
做了一个评论,暗示没有路径压缩(摊销O(log(n)
复杂性)的按等级联合对于大多数实际应用来说已经足够了。这是对的。我要问的是另一种方式:如果您按等级跳过联合并且只进行路径压缩怎么办?
从某种意义上说,路径压缩是按等级改进联合的额外步骤,这就是为什么可以省略该额外步骤而不会造成灾难性后果的原因。但是按等级联合是路径压缩的必要中间步骤吗?我可以跳过它并直接进行路径压缩,还是会是灾难性的?
还有人指出,如果没有按等级联合,重复联合可以创建类似链表的结构。这意味着单路径压缩操作可能会O(n)
在最坏的情况下进行。这当然会影响未来的运营,所以当摊销到许多运营中时,这将如何发挥作用是我更感兴趣的。
algorithm - 是否有 O(n) 整数排序算法?
上周我偶然发现了这篇论文,作者在第二页提到:
请注意,这会产生整数边权重的线性运行时间。
第三页也一样:
这产生了整数边权重的线性运行时间和基于比较的排序的 O(m log n)。
在第 8 页:
特别是,使用快速整数排序可能会大大加快 GPA。
这是否意味着在特殊情况下对于整数值存在 O(n) 排序算法?或者这是图论的专长?
PS:
参考文献 [3] 可能会有所帮助,因为在第一页他们说:
[..] 图类(例如整数边权重 [3]、[...]
但我无法访问任何科学期刊。
algorithm - 基本算术运算的大 O 复杂度
基本算术运算(如乘法、平方根、对数、标量和矩阵乘积)的广泛算法的 Big-O 复杂度是多少?
就大 O 复杂性而言,是否有更有效的奇异算法,但在实际解决方案中不是很普遍(例如,没有在流行的软件库中实现)?