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>的所有内容都是s.您需要针对"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- 集合中的数字元素)+它为事件绑定结构分配内存的成本.集合中的每个元素都将具有新绑定,因此分配了额外的内存.

所以总的答案是O(N*S)计算复杂性和M(N)内存消耗.

UAs通常做一些优化,但CSS选择器结构强制要求的最坏情况就是这样.

更新:为简洁起见,例如为"数据初始化"创建DOM属性节点等"小"事项被省略.