有没有办法在线性时间内连接2个表格?我听说这可以通过另一个数据结构(Hashtable)来完成,但我不确定如何做到这一点。我一直在想一个Join会涉及一个交叉产品,因此它是O(n^2)。在O(n)时间执行连接?
回答
算法:
循环遍历表A.将所有项目散列,将它们添加到Join数组中。
循环遍历表B,检查每个项目是否在散列表中(Check-O(1)),如果没有,则添加到联接表。
这取决于连接的类型。交叉连接总是会是O(n^2),因为它必须产生O(n^2)个记录。如果使用正确的数据结构,可以使用更好的复杂性(O(n log(n))或甚至可以摊销O(n))来完成等连接。
我一直在寻找自然连接的时间复杂度 – Shankar 2011-04-05 20:25:09
连接的类型并不重要。用两个不相交列表为每个记录添加一个值为0的共同虚拟列。自然连接的复杂性仍然是二次的,因此是最坏情况的估计。 – 2011-04-13 22:36:11
您可以通过使用散列表在另一个表的ID中查找记录,以接近O(n)的方式连接两个表。
嗯,实际上该操作将接近为O(n + m),其中Ñ和米是在两个表中的项数。您将首先遍历一个表中的记录以从该表中的键构建哈希表,然后循环遍历另一个表以在每个记录的哈希表中查找匹配项。
查找散列表中的项目不是O(1)操作,但它很接近。随着更多的数据你会有更多的散列冲突,所以一些查询需要做多个比较。
非常感谢回复 – Shankar 2011-04-05 20:28:12
很久以前,主要的数据库供应商不推荐使用散列索引。因此,在O(max(n,m))时间内连接2个表格实际上并不重要。对于标准B树索引,连接复杂度为O(min(n,m)* log(max(n,m))。
- 1. O =(N²)执行十次时较慢?
- 2. O(n)的运行时间算法
- 3. 时间复杂度O(N日志(log n)的)+ N O(L)
- 4. 时间复杂度 - O(n^2)到O(n log n)搜索
- 5. 时间复杂度:O(logN)或O(N)?
- 6. O(nlog * n)和O(n)之间?
- 7. haskell长度运行时间O(1)或O(n)
- 8. 下面的函数是O(n)时间和O(1)空间,其中n = | A |?
- 9. 找到O(1)的空间和O(n)的时间
- 10. 红黑树:在log(n)时间中拆分/连接时间
- 11. Binomial堆:证明合并运行在O(日志n)时间
- 12. 图的O(m + n)时间算法
- 13. 证明最大(O(f(n)),O(g(n)))= O(max(f(n),g(n))
- 14. 如何确定的时间复杂度为O(M + N)或O(Math.max(M,N))
- 15. 在O(N)
- 16. 如何根据与dplyr的时间间隔执行连接?
- 17. 嵌套for循环的运行时间是O(n^2)?
- 18. Ideal跳过列表? O(n)运行时间?
- 19. KSum如何最小运行时间为O(N^k-1)?
- 20. 追加程序O(n)的运行时间是?
- 21. 什么是运行时间?它是O(n)吗?
- 22. 具有O(n)时间复杂度的N皇后的解释?
- 23. if(N^2%N == 0)的大O符号的时间
- 24. 这是否解决O(N log(N))时间中的3SUM?
- 25. 在O(logn)时间使用STL堆执行减少键
- 26. 大O符号 - O(n日志(N))对O(的log(n^2))
- 27. 你如何看出O(log n)和O(n log n)之间的差异?
- 28. 我怎样才能找到与时间O(n)和空间O(1)
- 29. 发现许多不为O重复(n)的时间O(1)空间
- 30. 连接到CouchDB时强制执行连接超时
检查这一个http://en.wikipedia.org/wiki/Hash_join – Andrey 2011-04-05 20:21:13
[A (http://oreilly.com/catalog/9780596005733) – Pointy 2011-04-05 20:22:02
@Andrey和@Pointy:非常感谢你的链接:) – Shankar 2011-04-05 20:23:54