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

Question

假设没有疯狂的优化(我正在看你Chrome).

我说的是原始的,讨厌的,不打破 - 不要修复它,即v6 javascript,成本.

下限是:

document.getElementById()

与:

document.getElementsByTagName('div') lookup.

Answer 1

getElementById可以安全地假设O(1)在现代浏览器中,哈希表是id =>元素映射的完美数据结构.

没有任何优化任何简单的查询 - 无论是css选择器,id查找,类或标签名称查找 - 都不会比O(n)因为对所有元素的一次迭代总是足够糟糕.

但是,在一个好的浏览器中,我希望它有一个tagname => elements mapping,所以getElementsByTagName也是O(1)如此.

值得注意的是，`getElementsByTagName` 可以假设为 O(1)，因为它的返回类型 `HTMLCollection` 是实时的（也就是说，如果你向文档中添加了一个正确类型的新元素，你的 `HTMLCollection`在你背后更新），表明它将直接指向浏览器的内部结构。另一方面，最近更流行的 `querySelectorAll` 返回一个非活动的 `NodeList`，这意味着它每次都必须创建一个新的类数组对象，使其至少为 O(n)。（好吧，无论是那个还是插入都变得非常可怕。） (2认同)