ES6 集合：線性時間複雜度是強制性的嗎？

ES6 規範引入了鍵控集合，例如 Set、Map、WeakSet 和 WeakMap。這些集合提供了基於鍵存儲和檢索資料的有效方法。然而，問題出現了：規範是否要求這些集合上的操作具有線性時間複雜度？

線性時間複雜度或演算法選擇左開放

儘管期望廣泛接受的高性能演算法，例如Set 和Map 原型的O(1) 訪問，ES6 規範令人驚訝地為線性時間演算法敞開了大門。

該規範指出「集合物件必須使用平均而言提供次線性存取時間的[機制]來實現。」這種語言可以解釋為包括線性時間演算法。然而，它並沒有明確強制要求它們。

同樣，此規範也不排除效能較高的演算法，如雜湊表或平衡樹，它們提供對數時間複雜度。

缺乏明確的性能要求

規範中缺乏明確的性能要求引起了開發人員的關注，他們希望規範能夠快速確定優先級

但是，值得注意的是，該規範側重於可觀察的語義，例如可預測的迭代順序。雖然人們普遍期望基於哈希的高效實現，但該規範允許使用樹等替代資料結構，它提供對數時間複雜度。

結論

ES6 規範確實沒有明確要求對鍵控集合進行操作的線性時間複雜度。雖然在某些實作中可以觀察到線性時間演算法，但該規範為更高效能的實作留出了空間。開發人員應查閱特定瀏覽器或執行時間文檔，以了解這些集合操作在不同上下文中的實際時間複雜度。