我知道 HashMap 中的插入需要 O(1) 時間復雜度，因此對于插入“n”個元素，復雜度應該是 O(n)。我對下面的方法有點懷疑。請看一下。
private static Map<Character,Character> mapCharacters(String message){
Map<Character, Character> map = new HashMap<>();
char idx = 'a';
for (char ch : message.toCharArray()) { // a loop - O(n)
if (!map.containsKey(ch)) { // containsKey - take O(n) to check the whole map
map.put(ch, idx);
idx;
}
}
return map;
}
我正在做的是用順序 abcd 映射解密的訊息。
所以，我的困惑是上述方法的復雜度是 O(n^2) 還是 O(n)。請幫助我消除我的疑問。
uj5u.com熱心網友回復：
攤銷 O(n)。containsKey并且put都是攤銷 O(1); 請參閱java 中 HashMap.containsKey() 的時間復雜度是多少？尤其是。
uj5u.com熱心網友回復：
兩者的時間復雜度containsKey()將put()取決于equals/hashCode用作密鑰的物件的合同的執行情況。
在引擎蓋下，HashMap維護著一系列存盤桶。每個桶對應一個哈希范圍。每個非空桶包含節點（每個節點包含與特定映射條目相關的資訊），這些節點形成鏈表或樹（從 Java 8 開始）。
根據提供的密鑰的哈希確定正確存盤桶的程序幾乎是即時的，除非計算哈希的程序很繁重，但無論如何它被認為具有恒定的時間復雜度O(1)。訪問存盤桶（即訪問陣列元素）也是O(1)，但是事情會變得棘手。假設bucket只包含幾個元素，檢查它們不會顯著增加總成本（同時執行兩者時 ，我們應該檢查map中是否存在提供的keycontainsKey()put()) 和整體時間復雜度將為O(1)。
但是在所有映射條目由于某種原因最終都在同一個桶中的情況下，遍歷鏈表將導致O(n)，如果節點存盤為紅黑樹，則兩者的最壞情況成本containsKey()并且put()將是O(log n)。
如果Character作為關鍵，我們有一個正確的實作equals/hashCode。正確的散列函式對于確保物件在桶中均勻分布很重要。但是，如果您使用的hashCode()是損壞的自定義物件，例如總是回傳相同的數字，那么所有條目將最終在同一個存盤桶中，性能會很差。
碰撞，即不同物件在映射到同一個桶的范圍內產生哈希的情況是不可避免的，我們需要一個好的哈希函式來使碰撞的次數盡可能少，這樣桶就會被“均勻”占用當非空桶的數量超過負載因子時，地圖會擴大。
這種特定方法的時間復雜度是線性的O(n)。但是，如果您要更改密鑰的型別，則可能并非如此。
uj5u.com熱心網友回復：
鑒于您的原始代碼如下：
private static Map<Character,Character> mapCharacters(String message){
Map<Character, Character> map = new HashMap<>();
char idx = 'a';
for (char ch : message.toCharArray()) {
if (!map.containsKey(ch)) {
map.put(ch, idx);
idx;
}
}
return map;
}
以下是關于時間復雜度的一些觀察：
- 迭代每個字符
message將是 O(n) - 很明顯，如果有 10 個字符需要 10 步，10,000 個字符將需要 10,000 步。時間復雜度與 成正比n。 - 在回圈內部，您正在檢查地圖是否已經包含該字符 - 使用
containsKey()，這是一個定義為 O(1) 時間復雜度的恒定時間操作。這個想法是，無論您的地圖有 10 個鍵還是 10,000 個鍵，評估結果的實際時間都containsKey()應該相同。 - 在 里面
if，你有map.put()另一個恒定時間操作，另一個 O(1) 操作。 - 結合在一起：對于每個
nth角色，你花時間在回圈中迭代它，檢查地圖是否已經有了它，然后添加它；所有這些都是 3n（三倍n），即 O(n)。
另外，您可以通過替換此塊對代碼進行小幅改進：
if (!map.containsKey(ch)) {
map.put(ch, idx);
idx;
}
使用類似下面的內容（ idx僅當您放置某些內容時才會保留相同的運行行為，特別是如果前一個內容是“不存在”或可能已設定為“null” - 盡管“設定為 null”不'不適用于您的代碼示例）：
Character previousValue = map.putIfAbsent(ch, idx);
if (previousValue == null) {
idx;
}
盡管時間復雜度不會改變，但 usingcontainsKey()使代碼更清晰，并且還利用了免費提供的經過良好測驗的高性能代碼。
在幕后，呼叫Map.putIfAbsent()的實作方式如下（從 OpenJDK 17 開始）顯示初始呼叫，如果密鑰不存在，則get()隨后呼叫。put()
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/498088.html