Java基于二分搜索树、链表实现的集合Set复杂度分析 Java基于二分搜索树、链表的实现的集合Set复杂度分析实例详解

WFaceBoss 2021-04-21 我要评论

本文实例讲述了Java基于二分搜索树、链表的实现的集合Set复杂度分析。分享给大家供大家参考，具体如下：

两种集合类的复杂度分析

在Java底层基于二叉搜索树实现集合和映射和Java底层基于链表实现集合和映射中以二分搜索树和链表作为底层实现了集合Set，在本节就两种集合类的复杂度分析进行分析：
测试内容：Java底层基于二叉搜索树实现集合和映射和Java底层基于链表实现集合和映射中使用的书籍。
测试方法：测试两种集合类查找单词所用的时间

 //创建一个测试方法 Set<String> set:他们可以是实现了该接口的LinkedListSet和BSTSet对象
 private static double testSet(Set<String> set, String filename) {
  //计算开始时间
  long startTime = System.nanoTime();
  System.out.println("Pride and Prejudice");
  //新建一个ArrayList存放单词
  ArrayList<String> words1 = new ArrayList<>();
  //通过这个方法将书中所以单词存入word1中
  FileOperation.readFile(filename, words1);
  System.out.println("Total words : " + words1.size());

  //增强for循环，定一个字符串word去遍历words
  //底层的话会把ArrayList words1中的值一个一个的赋值给word
  for (String word : words1)
   set.add(word);//不添加重复元素
  System.out.println("Total different words : " + set.getSize());

  //计算结束时间
  long endTime = System.nanoTime();
  return (endTime - startTime) / 1000000000.0;//纳秒为单位
 }

 public static void main(String[] args) {
  //基于二分搜索的集合
  BSTSet<String> bstSet = new BSTSet<>();
  double time1 = testSet(bstSet, "pride-and-prejudice.txt");
  System.out.println("BSTSet:" + time1 + "s");
  System.out.println("————————————————————");
  //基于链表实现的集合
  LinkedListSet<String> linkedListSet = new LinkedListSet<>();
  double time2 = testSet(linkedListSet, "pride-and-prejudice.txt");
  System.out.println("linkedListSet:" + time2 + "s");

 }

结果：BSTSet的速度比LinkedListed的速度快