目標是找到字串中的第一個重復出現的字符。
下面的視頻中展示了兩種演算法，第一種演算法的時間復雜度為 n 平方。第二個演算法（從視頻中的 2:34 開始）在 O(n) 中運行。但我不明白為什么，因為每個新字符都需要與表中所有以前的字符進行比較，這將導致再次 n 平方的總運行時間。也許這里關于硬體（圖靈機）的假設很重要？
https://www.youtube.com/watch?v=GJdiM-muYqc
uj5u.com熱心網友回復：
但我不明白為什么，因為每個新字符都需要與表中所有以前的字符進行比較
訣竅是將一個字符與您及時看到的所有字符進行比較，這些字符與您檢查的字符數呈非線性關系。有多種方法可以做到這一點，例如使用哈希表或平衡樹。哈希集查找產生恒定時間，而平衡樹查找產生 log 2 n 時間。
為了說明這一點，請考慮一個僅由數字組成的字串。有十個可能的數字，因此“我以前見過這個數字”的測驗最多需要十個步驟，即使您已經檢查了一百萬個數字的字串。所有角色都可以做同樣的事情。
哈希表更進一步，因為它們放棄了由相對較小的東西限制的可能性數量的要求。平衡樹也是如此，盡管查找變為對數。
uj5u.com熱心網友回復：
我得到了答案。原因是可能的字符數有限。所以比較總是只需要固定的時間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/343575.html