给定两个列表l1,l2,显示如何在O(1)时间内合并它们.列表的数据结构取决于您的设计方式.通过合并,我的意思是说列表的联合.
例如:List1 = {1,2,3} List2 = {2,4,5}
合并清单= {1,2,3,4,5}
pol*_*nts 11
直接无法将两个已排序的列表合并到一个已排序的列表中O(1).
关于你能做的就是有一个"懒惰"的合并,可以点播提取每个连续元素最接近O(1),但执行的完全合并,它仍然是O(N)(这里N是元素的个数).
你可以做的是另一种物理接近的东西加入两个列表结束,结束在一个列表中,不进行合并算法无论如何,这样从一个列表中的所有元素从其他列表中的所有元素之前.事实上,这可以在O(1)(如果列表维护头部和尾部指针)中完成,但这不是传统定义的合并.
O(1)如果问题是关于什么样的集合表示允许联合操作O(1),那么是的,事实上可以这样做.在实践中有许多可能的集合表示,每个都有一些优点和缺点.
本专业代表性的一个重要例子是并查集,它允许O(?(n))对基本分期时间联盟和查找操作.?是Ackermann函数的反函数 ; 随着阿克曼函数的快速增长,其反转?增长非常缓慢.不相交集数据结构基本上O(1)为任何实际大小提供摊销操作.
需要注意的是"脱节"是这里的关键:它不能代表两套{1, 2, 3}及{2, 4, 5},因为这些集是不相交.不相交集合的数据结构表示的许多集(而不是两个),但没有两个不同的组被允许具有共同的元素.
另一种高度实用的集合表示是比特阵列,其中元件被映射到位的索引,和0/ 1分别表明不存在/存在.通过这种表示,联合只是一个按位OR ; 交叉点按位AND.渐近地,这不是最佳表示,但它在实践中可以是高度高效的集合表示.
您正在寻找的不是在O(1)时间内合并两个"列表" 的算法.如果您将"列表"视为"链接列表",那么这不能比O(n)更快地完成.
您要求查找的是用于存储此数据的数据结构,该数据结构支持在O(1)时间内合并.此数据结构不是列表.在"硬"O(1)时间内合并仍然是不可能的,但是有一些数据结构支持在摊销的 O(1)时间内合并.也许最着名的例子是Fibonacci Heap.