通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

在搜索中使用排序以提高效率

3636人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  小知识  | 

作者:因情语写

链接:https://www.proprogrammar.com/article/465

声明:请尊重原作者的劳动,如需转载请注明出处


    很多时候搜索可以和排序结合起来使用以提高效率,看个例子

  两个集合

  A = {5,2, 4, 7}

  B = {5,3,2,1,6,9,7,4}

  判断A是否是B的子集

  一般的暴力解法直接用双层循环一个元素一个元素比较,复杂度为n平方

  可以先排序再判断,排序复杂度为nlogn,再进行比较,如何比较

  A : 2 4 5 7

  B : 1 2 3 4 5 6 7 9

  比较过程如下:

  A : 2     4     5     7

     ^
  B : 1     2     3     4    5     6    7     9

        ^

  不同,B小,B取下个元素

  A : 2    4     5     7

     ^
  B : 1    2     3    4     5     6    7     9

           ^

  相同,A取下个元素

  A : 2    4     5     7

          ^
  B : 1     2    3     4    5    6    7    9

              ^

  A : 2    4     5     7

          ^
  B : 1     2     3    4    5    6    7    9

                     ^

  A : 2    4     5    7

           ^
  B : 1     2    3    4     5    6    7     9

                         ^

  相同,A取下个元素

  A : 2     4    5     7

                 ^
  B : 1    2    3     4     5    6    7     9

                         ^

  A : 2     4     5    7

                  ^
  B : 1    2    3     4    5     6    7    9

                               ^

  相同,A取下个元素

  A : 2    4     5    7

                        ^
  B : 1     2    3     4     5    6     7    9

                                  ^

  A : 2     4     5     7

                          ^
  B : 1    2     3     4    5     6     7    9

                                       ^

  A : 2     4    5    7

                        ^
  B : 1     2    3     4    5     6    7    9

                                              ^

  相同,比较完毕

  可见,最多只要遍历A和B一遍就可以得出结果


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告