标签: time-complexity

正如TimeComplexity文档中所见,Python的list类型实现使用数组.

因此,如果正在使用数组并且我们做了一些追加,最终您将不得不重新分配空间并将所有信息复制到新空间.
毕竟,怎么可能是O(1)最坏的情况？

二进制搜索树对具有二分搜索的排序数组有什么好处？只是通过数学分析我没有看到差异,所以我假设低级实现开销必须存在差异.平均病例运行时间的分析如下所示.

使用二进制搜索
搜索的排序数组:O(log(n))
插入:O(log(n))(我们运行二进制搜索以查找插入元素的位置)
删除:O(log(n))(我们运行二进制搜索找到要删除的元素)

二进制搜索树
搜索:O(log(n))
插入:O(log(n))
删除:O(log(n))

对于上面列出的操作,二进制搜索树具有最坏的O(n)情况(如果树不平衡),所以这看起来实际上比使用二进制搜索的排序数组更差.

另外,我不假设我们必须预先对数组进行排序(这将花费O(nlog(n)),我们将逐个插入元素到数组中,就像我们对二叉树所做的那样.唯一的好处BST我可以看到它支持其他类型的遍历,如inorder,preorder,postorder.

最初的问题陈述是这样的:

给定一个32位无符号整数数组,其中每个数字除了其中三个(恰好只出现一次)之外恰好出现两次,使用O(1)额外空格在O(n)时间内找到这三个数字.输入数组是只读的.如果有k个例外而不是3个怎么办？

如果由于输入限制(阵列最多可以包含2 ³³个条目)而接受非常高的常数因子,则很容易在?(1)时间和?(1)空间上解决这个问题:

for i in lst:
    if sum(1 for j in lst if i == j) == 1:
        print i

因此,为了这个问题,让我们放弃比特长度的限制,并专注于数字可以达到m比特的更普遍的问题.

推广k = 2的算法,我想到的是以下内容:

1. 对具有最低有效位的那些数字1和具有0单独的那些数字进行异或.如果对于两个分区,结果值不为零,我们知道我们已将非重复数字划分为两个组,每个组至少有一个成员
2. 对于每个组,尝试通过检查第二个最低有效位等进一步对其进行分区

不过,有一个特殊情况需要考虑.如果在对一个组进行分区后,其中一个组的XOR值都为零,我们不知道其中一个结果子组是否为空.在这种情况下,我的算法只是将该位丢弃并继续下一个,这是不正确的,例如它输入失败[0,1,2,3,4,5,6].

现在我的想法是不仅要计算元素的XOR,还要计算应用某个函数后的值的异或(我在f(x) = 3x + 1这里选择).有关此附加检查的反例,请参阅下面的Evgeny的答案.

现在虽然以下算法对于k> = 7是不正确的,但我仍然在这里包含实现以给你一个想法:

def xor(seq):
  return reduce(lambda x, y: x ^ y, seq, 0)

def compute_xors(ary, mask, bits):
  a = xor(i for i in ary if i …

我正在尝试评估是否比较两个字符串随着它们的长度增加而变慢.我的计算建议比较字符串应该采用摊销的常数时间,但我的Python实验会产生奇怪的结果:

下面是字符串长度(1到400)与时间(以毫秒为单位)的关系图.禁用自动垃圾收集,并gc.collect在每次迭代之间运行.

我每次比较100万个随机字符串,计算匹配如下.过程重复50次,然后取所有测量时间的min.

for index in range(COUNT):
    if v1[index] == v2[index]:
        matches += 1
    else:
        non_matches += 1

什么可能解释长度64附近的突然增加？

注意:下面的代码片段可以用来尝试重现假设问题v1和v2是长的随机字符串的两个列表n和COUNT是它们的长度.

timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
  "from __main__ import COUNT, v1, v2", number=50)

进一步说明:我做了两个额外的测试:比较字符串is而不是==完全抑制问题,性能大约是210ms/1M比较.由于已经提到实习,我确保在每根弦之后增加一个空格,这样可以防止实习; 这不会改变任何事情.那不是实习吗？

我最近了解了处理哈希表中冲突的不同方法.并且看到链接列表的单独链接总是更节省时间,并且为了节省空间,我们为线性探测分配预定义的内存,稍后我们可能不会使用,对于单独的链接我们动态地利用内存,因此是与链表单独链接不比线性探测更有效吗？如果是的话我们为什么要使用线性探测呢？

简介:据我所知,此问题尚未在SO中提出.
这是一个面试问题.
我甚至没有专门寻找代码解决方案,任何算法/伪代码都可以工作.

问题:给定一个整数数组int[] A及其大小N,找到2个非后续(在数组中不能相邻)元素的总和最小.答案也必须不包含第一个或最后一个元素(索引0和n-1).解决方案也应该是O(n)时间和空间的复杂性.

例如,当A = [5, 2, 4, 6, 3, 7]答案是5,从那以后2+3=5.
如果A = [1, 2, 3, 3, 2, 1]答案是4,因为2+2=4你不能选择使用的的1的,因为是在阵列的两端.

尝试:起初我认为解决方案中的一个数字必须是数组中最小的数字(除了第一个和最后一个),但这很快反驳了反例
A = [4, 2, 1, 2, 4] -> 4 (2+2)

然后我想如果我找到数组中的2个最小数字(除了第一个和最后一个),解决方案将是那两个.这显然很快就失败了,因为我不能选择2个相邻的数字,如果我必须选择不相邻的数字,那么这就是问题的定义:).

最后我想,好吧,我将在数组中找到3个最小的数字(除了第一个和最后一个),解决方案必须是其中的两个,因为其中两个必须不相互相邻.这也失败了A = [2, 2, …

任何人都可以给我一个网站的引用,其中包含主要Java数据结构的摘要,以及它们各自的复杂性(对于某些给定的操作,如添加,查找,删除),例如Hashtables是O(1)用于查找,而LinkedLists在...上).像内存使用这样的一些细节也会很好.

这对于在算法的数据结构中进行思考非常有用.

可能重复:
如何在两个排序数组的并集中找到第k个最小元素？

这是一个问题,我的一位朋友告诉我他在面试时被问到,我一直在考虑解决方案.

次线性时间对我来说意味着对数,所以也许是某种分而治之的方法.为简单起见,假设两个数组的大小相同,并且所有元素都是唯一的

有人知道ECMAScript5的Object.keys()在常见实现中的时间复杂度吗？它是O(n)用于n钥匙？假设哈希实现,时间是否与哈希表的大小成比例？

我正在寻找语言实现者或某些现实世界基准测试的保证.

是否有任何Python复杂性参考？例如,在cppreference中,对于许多函数(例如std :: array :: size或std :: array :: fill),有一个复杂性部分,用容器大小的线性或常量来描述它们的运行复杂性..

我希望在python网站上出现相同的信息,或许至少对于CPython实现.例如,在列表引用中,list.insert我希望看到复杂性:线性 ; 我知道这种情况(和许多其他容器相关的操作)在这里,但许多其他情况不是.这里有一些例子:

• 什么是复杂性tuple.__le__？似乎在比较两个大小的元组时n,k复杂性是关于O(min(n,k))(然而,对于小n的它看起来不同).
• 什么是复杂性random.shuffle？它似乎是O(n).它也出现了复杂random.randint的O(1).
• __format__字符串方法的复杂性是什么？它看起来与输入字符串的大小呈线性关系; 然而,当数也增长有关生长参数(比较("{0}"*100000).format(*(("abc",)*100000))用("{}"*100000).format(*(("abc",)*100000))).

我知道(a)这些问题中的每一个都可以单独回答,(b)可以查看这些模块的代码(即使有些是用C语言编写的),(c)StackExchange不是python邮件用户请求列表.所以:这不是文档功能请求,只是两个部分的问题:

1. 你知道这样的资源是否存在吗？
2. 如果没有,你知道要求的地方是什么,或者你能说出我不需要的地方吗？