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

What is the time complexity of HTML DOM lookups

本文关键字：多少时间复杂度 DOM 查找 HTML 更新时间：2023-09-26

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

我说的是原始的，讨厌的，没有破产的，不要修复它，即v6 javascript，成本。

下限为：

document.getElementById()

对：

document.getElementsByTagName('div') lookup.

可以

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

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

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