标签: time-complexity

我正在研究数据结构课程,我不知道如何继续这个Big O分析:

sum = 0;
for(i = 1; i < n; i++)
     for(j = 1; j < i*i; j++)
         if(j % i == 0)
             for(k = 0; k < j; k++)
                   sum++;

我最初的想法是在减少之后这是O(n ^ 3),因为最里面的循环将仅在j/ i没有余数时运行并且乘法规则不适用.我的推理在这里是否正确？

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

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

第三页上的内容相同:

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

在第8页:

特别是,使用快速整数排序可能会显着加速GPA.

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

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

[...]图表类已经实现了进一步的改进,例如整数边权重[3],[...]

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

我目前正在通过在线学习你的Haskell书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？

n log n > n- 但这就像是一段pseudo-linear感情.如果n=1 billion,log n~30;

所以,n log n将30 billion是30 X n,顺序n.我想知道这个时间复杂度之间n log n and n的差异在现实生活中是否显着.

例如:quick select在未排序数组中查找第k个元素是O(n)使用快速选择算法.

如果我对数组进行排序并找到第k个元素,那就是O(n log n).要排序一个数组1 trillion的元素,我会很60 times慢,如果我做quicksort和index it.

运营商的时间复杂度是delete[]多少？

我的意思是它是如何实现的 - 它是否迭代数组中的所有元素并为每个元素调用析构函数？

此运算符是否对基本类型(int等)和用户定义的类型执行相同操作？

由JS标准共同定义的运行复杂Array的功能,如push,pop,shift,slice或splice？ESP.我有兴趣在随机位置删除和插入条目.如果未定义复杂性,我可以期待什么,例如在V8中？

(这个问题的灵感来自于此.此外,这个贴在这里的基准也让我很好奇,但也许这是一些无关的现象.)

(一个非常相关的问题在这里.但是,对接受的答案的评论之一说现在是错误的.另外,接受的答案没有任何参考标准真正定义它的方式.).

感谢来自这里的人们的帮助,我能够获得塔斯马尼亚骆驼拼图工作的代码.然而,它非常慢(我想.我不确定,因为这是我在Python中的第一个程序).在代码底部运行的示例需要很长时间才能在我的机器中解决:

dumrat@dumrat:~/programming/python$ time python camels.py
[['F', 'F', 'F', 'G', 'B', 'B', 'B'], ['F', 'F', 'G', 'F', 'B', 'B', 'B'],
 ['F', 'F', 'B', 'F', 'G', 'B', 'B'], ['F', 'F', 'B', 'F', 'B', 'G', 'B'],
 ['F', 'F', 'B', 'G', 'B', 'F', 'B'], ['F', 'G', 'B', 'F', 'B', 'F', 'B'],
 ['G', 'F', 'B', 'F', 'B', 'F', 'B'], ['B', 'F', 'G', 'F', 'B', 'F', 'B'],
 ['B', 'F', 'B', 'F', 'G', 'F', 'B'], ['B', 'F', 'B', 'F', 'B', 'F', 'G'],
 ['B', 'F', 'B', 'F', 'B', …

在最坏的情况下contains,单个查找操作OR 是否O(n)合适？那么,对于n元素的查找hashSet会是O(n^2)什么？

在Python中,in关键字的效率是多少,例如:

a = [1, 2, 3]
if 4 in a:
  ...

我已经注意到python官方网站上设置操作的时间复杂性表.但我只是想问一下将列表转换为集合的时间复杂度,例如,

l = [1, 2, 3, 4, 5]
s = set(l)

我知道这实际上是一个哈希表,但它究竟是如何工作的呢？那是O(n)吗？