关于selector选择符解析的方法

先推荐关于js selector的好文章

http://www.never-online.net/blog/article.asp?id=295

http://www.never-online.net/blog/article.asp?id=296

这里只讨论没有特殊位置关系的情况，第一种方案是常规的从左往右查

例如对于 div p

采用普通的查找过程如下：

1. 先查找页面上所有的div
2. 循环所有的div，查找每个div下的p
3. 合并结果

由于dom节点的数据结构是一棵树，对于这种查找方法，算法的时间复杂度为O(N^2)，N为节点总数

另一种方案是从右往左查，这也是一些浏览器引擎采用的方法

这种方法的查找过程如下：

1. 先查找页面上所有的p
2. 循环所有的p，查找每个p的父元素

    如果不是div，遍历上一层。
        如果已经是顶层，排除此p。
        如果是div，则保存此p元素。

可以证明，这种方案的算法时间复杂度降低到Ｏ(N*logN)

但是有没有别的的方法呢？

答案是有----

还是按照从左到右的方法查，但是，先对 div div进行一次除重，即只保留最外层的div

理由是，命题div div a => div a为真

所以：

1.先找出所有的div元素，对这些div元素进行遍历，删掉那些祖先元素为div的div

这个算法看起来是O(N^2)的，但是实际上不是，因为----

document.getElementsByTagName('div') 获得的节点不是完全无序的，而一定是祖先在前子孙在后，并且是深度优先遍历的

所以有如下定理：

集合[div1, div2, div3... div(n)] 是 document.getElementsByTagName('div')的查询结果

若 div(k) 不是div1的子孙，则div(k+1) div(k+2)… div(n) 都不是div(k)的子孙

所以，除重算法如下：

var divs = document.documentElement.getElementsByTagName("div");
    divs = makeArray(divs);

    for (var i=1; i<divs.length; i++) {
      if (dom_contains(divs[i-1], divs[i])) {
      //除重，复杂度N。
      //如果dom里前者包含后者，则移者后者
      //当前循环标记-1
      //结果将是
      //第一轮：[1,3,4,5,6], i=1
      //第二轮：[1,4,5,6] i=1
      //第三轮：[1,5,6] i=1
      //第四轮：[1,6] i=1
      //第五轮：[1] i=1
        divs.splice(i,1);
        i--;
      }
    }

可以看出这是一个O(N)复杂度的除重算法

进行完这个除重之后，只需要将除重后的div的子孙p合并起来即可

这样整个算法就简化为O(N)，成为一种更高效率的方法