有沒有辦法在線性時間內連接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