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

0 投票
2 回答
2588 浏览

complexity-theory - 关于独立集问题的NP-完全性问题

我认为,当证明一个问题 P 是 NP-Complete 时,我们应该将一个已知的 NPC 问题简化为 P。但是,看看独立集问题的解决方案,它似乎不是这样。

为了证明独立集是 NP 完全的,你需要一个图 G,找到它的逆 G',然后计算 CLIQUE(G')。但是,这是相反的:它处理一个问题 PI 不知道它是否是 NPC,然后将其简化为已知 NPC 问题。

是解决方案的一个示例。

我在这里想念什么?这难道不是错的,因为它是反过来做的吗?

0 投票
5 回答
7635 浏览

binary-search - 优先级队列 O(n) 的排序列表实现的插入时间复杂度?

来自维基百科

排序列表实施:就像超市的收银台,但重要的人可以在不太重要的人面前“剪掉”。( O(n) 插入时间, O(1) 获取-下一次, O(n*log(n)) 构建)

我认为如果用二分查找算法搜索插入位置,插入时间复杂度应该是O(log(n))。这里我把作业的到达顺序作为一个优先因素。

那么我错了还是维基百科不正确?

更新:根据 TAOCP 对列表的严格定义:

线性列表是 n >=0 节点 X 1 , X[2], ... , X[n] 的序列,其基本结构属性仅涉及项目之间出现在一行中的相对位置。

我假设列表wikipedia 引用不是linked-list,它可能是array

谢谢。

0 投票
6 回答
99205 浏览

java - java ArrayList 的时间复杂度

java中是ArrayList数组还是列表?get 操作的时间复杂度是多少O(n)O(1)

0 投票
6 回答
1139 浏览

time-complexity - 时间复杂度混淆

我一直对此感到有些困惑,可能是由于我对编译器缺乏了解。但是让我们以 python 为例。如果我们有一些名为 numlist 的大型数字列表,并且想要删除任何重复项,我们可以在列表上使用集合运算符,例如 set(numlist)。作为回报,我们将获得一组数字。据我所知,此操作将在 O(n) 时间内完成。虽然如果我要创建自己的算法来处理这个操作,我所希望的绝对最好的结果是 O(n^2)。

我没有得到的是,是什么允许像 set() 这样的内部操作比语言算法的外部操作快得多。检查仍然需要完成,不是吗?

0 投票
6 回答
385 浏览

algorithm - 计算算法复杂度 - 混乱

我有以下代码片段:

复杂性会是O(n^2),但如果我想进一步挖掘内部循环的复杂性,那么它会是(n (n-1))/2还是(n-1)!

0 投票
5 回答
2782 浏览

algorithm - 使用多项式时间的“最难”问题是什么?

最近我读了一篇研讨会的作品,上面写着:

匹配算法[用于一般图]可以扩展到加权情况,这似乎是可以在多项式时间内解决的“最难”的组合优化问题之一。

我立刻想到了以下问题:

你知道其他“P-hard”问题吗?

现在我想将 P-hard 定义为:“在该问题的文献中很晚才(1950 年之后)发现了多项式算法”。(或者如果已经有一种确定性算法可以在多项式时间内解决问题,那么如何更好地定义“困难”?)

0 投票
31 回答
1308902 浏览

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,但我不明白如何识别具有对数时间的函数。

0 投票
2 回答
5701 浏览

algorithm - 不相交集森林数据结构的无秩联合/查找算法

以下是wikipedia上不相交集森林的联合/查找算法的细分:

  • 准系统不相交的森林... ( O(n))
    • ...按等级联合...(现在改进为O(log(n)
      • ... 带有路径压缩(现在改进为O(a(n)), 有效O(1)

按等级实现联合需要每个节点保留一个rank字段以进行比较。我的问题是,按等级联合是否值得这个额外的空间?如果我按等级跳过联合而只进行路径压缩会发生什么?够好吗?现在的摊销复杂度是多少?


做了一个评论,暗示没有路径压缩(摊销O(log(n)复杂性)的按等级联合对于大多数实际应用来说已经足够了。这是对的。我要问的是另一种方式:如果您按等级跳过联合并且只进行路径压缩怎么办?

从某种意义上说,路径压缩是按等级改进联合的额外步骤,这就是为什么可以省略该额外步骤而不会造成灾难性后果的原因。但是按等级联合是路径压缩的必要中间步骤吗?我可以跳过它并直接进行路径压缩,还是会是灾难性的?


还有人指出,如果没有按等级联合,重复联合可以创建类似链表的结构。这意味着单路径压缩操作可能会O(n)在最坏的情况下进行。这当然会影响未来的运营,所以当摊销到许多运营中时,这将如何发挥作用是我更感兴趣的。

0 投票
6 回答
67720 浏览

algorithm - 是否有 O(n) 整数排序算法?

上周我偶然发现了这篇论文,作者在第二页提到:

请注意,这会产生整数边权重的线性运行时间。

第三页也一样:

这产生了整数边权重的线性运行时间和基于比较的排序的 O(m log n)。

在第 8 页:

特别是,使用快速整数排序可能会大大加快 GPA。

这是否意味着在特殊情况下对于整数值存在 O(n) 排序算法?或者这是图论的专长?

PS:
参考文献 [3] 可能会有所帮助,因为在第一页他们说:

[..] 图类(例如整数边权重 [3]、[...]

但我无法访问任何科学期刊。

0 投票
7 回答
7596 浏览

algorithm - 基本算术运算的大 O 复杂度

基本算术运算(如乘法、平方根、对数、标量和矩阵乘积)的广泛算法的 Big-O 复杂度是多少?

就大 O 复杂性而言,是否有更有效的奇异算法,但在实际解决方案中不是很普遍(例如,没有在流行的软件库中实现)?