假设没有任何疯狂的优化（我在看你，Chrome）。
我所说的是纯粹的、恶劣的、不修补就不会出问题的JavaScript v6成本。
下限为：
document.getElementById()
对比：
document.getElementsByTagName('div') lookup.
HTML DOM查找的时间复杂度是什么？
21
- Evan Plaice
2
1如果你正在为IE 6进行优化，我建议你重新考虑“不需要修复”的部分。 - robrich
@robrich 我并没有进行任何优化。只是好奇。我认为ie6会标记“没坏”后面的讽刺意味。也许我应该用“引号”来表明清晰度。 - Evan Plaice
1个回答
25
getElementById可以在现代浏览器中安全地假定为O(1)，因为散列表是id => element映射的完美数据结构。
没有任何优化时，任何简单的查询（无论是css选择器、id查找、类名或标记名称查找）都不会比O(n)差，因为只需要一次迭代遍历所有元素。
然而，在好的浏览器中，我希望它有一个标签名称=>元素映射，因此getElementsByTagName也将是O(1)。
- ThiefMaster
4
1即使在最好的情况下，没有任何优化的getElementsByTagName函数的时间复杂度也将是O(n)，因为最后一个元素可能就是你要查找的元素。 - Rune FS
那么，这是否意味着浏览器在写入时为每个标记映射多个视图以最大化读取速度？那样会不会稍微更加占用内存？ - Evan Plaice
这些映射的内存使用量是无关紧要的。它比在内存中缓存的单个图像（例如网站上的背景图像）要少得多。 - ThiefMaster
3值得注意的是，可以假定
getElementsByTagName的时间复杂度为O(1)，因为它返回的类型是HTMLCollection，这个集合是实时的（也就是说，如果你往文档中添加了一个正确类型的新元素，你的HTMLCollection会在背后自动更新），这表明它将直接指向浏览器的内部结构。另一方面，最近更流行的querySelectorAll返回一个非实时的NodeList，这意味着每次都需要创建一个新的类似数组的对象，使其至少为O(n)。（嗯，要不然插入操作就变得非常可怕了。） - Chris Morgan网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接