與蠻力相比，為什麼查找表會加快速度？
我目前正在閱讀查找表和效率。在我的 uni 腳本中，它說：
對於蠻力：
- 準備時間： $ O(1) $
- 磁碟空間要求： $ O(1) $
- 破解密碼所需時間： $ O(2^n) $
完整查找表：
- 準備時間： $ O(2^n) $
- 磁碟空間要求： $ O(2^n) $
- 破解密碼所需時間： $ O(1) $
我不確定我是否正確理解了這一點。
據我了解，對於蠻力：
$ O(1) $ 是在我的所有可能密碼表中查找密碼所需的時間。磁碟空間要求與所有可能密碼列表所需的一樣大，因此 $ O(1) $ 以及
我的問題：
為什麼破解密碼需要時間 $ O(2^n) $ ? 它是如何確定的？
看來我也不明白查找表的概念。據我所知，查找表將簡單地散列可能密碼的完整列表（因此所需的磁碟空間更大），但那又如何呢？為什麼密碼本身的破解速度更快？
我想我在這裡遺漏了一些重要的東西。任何幫助將不勝感激。
假設你有一個 $ n $ 位密鑰。進一步假設你有一些可靠的謂詞 $ P(k,m) $ 決定一個鍵是否 $ k $ 是給定參考的關鍵 $ m $ . 此外，假設您有一個“繼任者”功能 $ F $ ，它需要一個鍵並返回“下一個”鍵，以便最終遍歷所有鍵。
現在暴力攻擊的作用是，給定 $ m $ , 它需要一個啟動鍵 $ k $ , 評估 $ P(k,m) $ 如果返回 false，則設置 $ k\gets F(k) $ . 這將需要 $ \mathcal O(2^n) $ 的評價 $ P $ 和 $ F $ . 假設兩者都可以計算 $ \mathcal O(1) $ 整個計算需要 $ \mathcal O(2^n) $ .
現在是查找表。為此，您只需從某個關鍵點開始 $ k $ ，並儲存 $ m $ 這樣 $ P(k,m) $ 成對產生 true $ (m,k) $ 在一個巨大的數組（或hashmap）中。現在你重複這個 $ F(k) $ . 當你得到一個混凝土 $ m $ ，你只需在表格中查找並找到對應的 $ k $ . 對於 hashmap 和連續數組，這需要時間 $ \mathcal O(1) $ （即查找時間與元素的數量無關）。顯然，您需要儲存所有 $ 2^n $ 對 $ (m,k) $ . 現在準備時間假設你可以找到 $ m $ 這樣 $ P(k,m) $ 是的，但這通常在恆定時間內是可能的，例如通過評估散列函式或加密密碼。