我最近聽說過關於nedtries並決定嘗試實現它們，但是一些讓我困擾的是他們搜索操作的複雜性;我不明白爲什麼他們應該這麼快。nedtrie上的搜索操作的複雜性（逐行搜索結果）
根據我的理解，他們的搜索操作的預期複雜度應該是 O（m/2），其中密鑰的大小以位爲單位。 如果在傳統的二進制樹比較它的搜索操作的複雜性， 你： 的log 2（N）> = M/2
讓我們的重點是32位長：LOG 2（N）> = 16 < => n> = 65536
因此，從65536個項目開始，所有的項目都應該比二叉樹更快。然而，作者聲稱他們總是比二叉樹快，所以無論是我的假設 對他們的複雜性都是錯誤的，或者在搜索的每一步執行的計算在網上都快得多。
那麼，它呢？
如果你有更小的樹，你可以使用更小的鍵！
（注意我是作者的nedtries）。我認爲我在頁面前面的複雜性解釋是合理的？也許不是。
您缺少的關鍵是它確定複雜度的位之間的差異。差異越大，搜索成本越低，而差異越小，搜索成本越高。
這個作品的實際情況源於現代無序處理器。簡單地說，如果你避開主存，你的代碼運行速度比依賴主存更快40-80倍。這意味着你可以在從內存中加載單個東西所需的時間內執行50-150個操作。這意味着您可以進行一次掃描並找出我們應該繼續查看的節點，而不會比將該節點的緩存線加載到內存中的時間長得多。
這有效地消除了複雜性分析中的邏輯，位掃描和其他一切。他們都可能是O（N^N），並不重要。現在最重要的是，選擇下一個要查看的節點是有效的，因此必須加載的節點數量是縮放約束，因此它是從總數中查看的平均節點數量這是其平均複雜度的節點，因爲主存緩慢是迄今爲止最大的複雜性約束。
這是否有意義？這意味着奇怪的是，如果某些位密集包裝在密鑰的一端而鬆散地包裝在密鑰的另一端，那麼密集包裝的一端的搜索將非常慢（接近O（log N），其中N是數字的密集元素）比在鬆散包裝的末尾搜索（接近O（1））。
不久之後，我將着手添加利用這種按位嘗試功能的新功能，因此您可以說「將此節點添加到鬆散/密集的空間並返回您選擇的密鑰」以及各種類型在這個主題上的變化。可悲的是，一如既往，這取決於時間和對時間的要求。
尼爾
簡單而高效。完美的答案。 – fokenrute 2010-12-03 09:16:20