javascript - HTML DOM 查找的时间复杂度是多少

Question

假设没有疯狂的优化（我在看你的 Chrome）。

我说的是原始的、讨厌的、不坏的、不修复的，即v6 javascript，成本。

下限为：

document.getElementById() 

相对：

document.getElementsByTagName('div') lookup.

Answer 1

getElementById可以安全地假设O(1)在现代浏览器中，因为哈希表是 id=>element 映射的完美数据结构。

如果没有任何优化，任何简单的查询——无论是 css 选择器、id 查找、类或标签名称查找——都不会比O(n)所有元素的一次迭代更糟糕。

然而，在一个好的浏览器中，我希望它有一个 tagname=>elements 映射，所以getElementsByTagName也是O(1)如此。