我正在制作一種應該在記憶體中運行的類似第四種語言的地方是一種溢價。
由于空間限制和缺乏可調整大小的記憶體，該語言使用鏈接串列作為其語言單詞詞典。
然而，一想到鏈表查找的性能成本，我就心疼。我知道最壞的情況總是 O(n)，但是當我意識到一些事情時，我試圖想辦法至少改進典型情況：如果“查找”方法除了查找密鑰之外，還每次擊鍵時執行一次類似冒泡排序的操作。這樣，最常見的鍵將“冒泡”到頂部。更好的是，隨著編譯的繼續，整個串列將重新加權，并且應該與鍵的連續統計可能性大致相關。
這種技術是否在其他地方使用過？我很好奇它的運行時復雜性是否有一個像樣的數學證明（假設一些名稱與其他名稱的統計曲線）。單個冒泡排序操作顯然是 O(1)，因此至少它不會損害理論上的運行時復雜性。
uj5u.com熱心網友回復：
雖然這種策略應該可以提高常見情況下的平均運行時間，但這并不會改變最壞情況下的復雜度，即O(n).
實際上，如果搜索到的鍵位于 size 串列的末尾，則nfind 將O(n)及時運行。氣泡交換操作O(1)及時運行（假設密鑰實際上可以在恒定時間內進行比較）。如果提取了相同的鍵但仍然是 ，則下一個查找操作會更快一些O(n)。取到同一個key后n，可以及時取到這個key O(1)。但是，n以特定順序獲取其他鍵可以重新排序串列，以便將初始鍵放在末尾。更具體地說，獲取初始關鍵時間旁邊的專案可以n做到這一點。最后，以特定順序獲取n初始鍵和n其他鍵的時間導致(n n-1 n-2 ... 2 1) (1 2 ... n-1 n) = n*(n-1) = n2-n = O(n2)操作。在這些操作之后，串列應該處于與初始串列相同的狀態。因此，復雜性是顯而易見的O(n)。
請注意，您可以實作快取以加快獲取速度。存在許多政策。您可以在此處找到其中的一些描述。請注意，這不會影響復雜性，但肯定會大大縮短執行時間。快取可以將迭代器存盤到鏈表的節點。插入/洗掉專案時迭代器不會失效（除非實際洗掉了目標專案）。
另請注意，鏈表通常非常慢。它們在記憶體使用方面也不是很有效，因為指向下一項的指標占用了一些空間（在 64 位架構上為 8 個位元組）。分配的節點也可能需要一些關于使用的標準庫分配器的隱藏空間（一些存盤指標元資料，如分配的空間）。使用更少記憶體的解決方案是使用包含鍵值對桶的鏈表。
請注意，雖然平衡二叉搜索樹需要更多記憶體，但它們可以更有效地解決這個問題。在這種資料結構中找到一個鍵的復雜度是O(log n). 一個好的哈希映射實作在記憶體中也可以非常緊湊（請參閱hopscotch hashing），盡管哈希映射的記憶體消耗在調整大小時可能會非常大。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/435990.html