javascript - jQuery 表达式的复杂性

Question

我正在阅读这篇文章 - http://css-tricks.com/interviewing-front-end-engineer-san-francisco - 关于面试前端工程师。写这篇文章的人建议如下:

与其询问合并排序的复杂性，不如询问这个 jQuery 表达式的复杂性:

$("#nav a")
  .addClass("link")
  .attr("data-initialized", true)
  .on("click", doSomething)

他继续说:对此问题的正确回答将展示对基本计算机科学原理的理解以及对 jQuery 在幕后所做工作的更深入了解。

那么，正确答案是什么？

(我实际上会发现谈论合并排序的复杂性(Big O)更容易，尽管我已经有一段时间没有对算法进行任何真正的分析了。自从大学以来就没有了!)

Answer 1

这里是一行一行的:

("#nav a") - 查找匹配的元素是 O(N)任务一般。考虑到 #nav 被分配给了 body 元素，而您文档中的所有元素都是 <a>。秒。您需要针对“a”选择器扫描所有这些。

.addClass("link") - 那是 O(n)只是浏览列表的任务。但它有隐藏的成本 - 通过更改元素的类，您要求浏览器重新计算元素及其所有后代的样式。所以在最坏的情况下，所有 DOM 元素都会受到影响。考虑到样式重新计算的成本是 O(N*S)任务(N - DOM 元素的数量，S - 所有样式表中样式规则的数量)那么总价将为 O(N*S)

.attr("data-initialized", true) - 原则上与上述价格相同。

.on("click", doSomething) - 即 O(n)任务(n - 集合中的数字元素)+ 它具有为事件绑定(bind)结构分配内存的成本。集合中的每个元素都会有新的绑定(bind)，因此会分配额外的内存。

所以总体答案是O(N*S)计算复杂性和M(N)用于内存消耗。

UA 通常会做一些优化，但 CSS 选择器结构要求的最坏情况就是这样。

更新:为了简洁起见，诸如为“数据初始化”创建 DOM 属性节点之类的“小”事情被省略了。