最快的 HTML 解析算法的时间复杂度是多少？我需要大 O 符号

Question

正如标题所说，我需要知道最快的 HTML 解析算法的时间复杂度。

更新：我需要从 HTML 代码创建 DOM 树的复杂性，而不仅仅是解析它。

Answer 1

HTML DOM 构造应该是正确嵌套输入的线性时间。然而，AngleSharp 声称实现的 Html5 算法需要通过所谓的“采用代理算法”（AAA）对不正确嵌套的内容进行特定处理，该算法需要通过未闭合的格式元素堆栈进行线性搜索。尽管试图限制损害（有关历史，请参阅此 W3C 讨论主题），但可以制作算法需要二次时间的 HTML 文档。