Java基于二分搜索樹、鏈表如何實(shí)現(xiàn)集合Set復(fù)雜度分析

小編給大家分享一下Java基于二分搜索樹、鏈表如何實(shí)現(xiàn)集合Set復(fù)雜度分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

你所需要的網(wǎng)站建設(shè)服務(wù)，我們均能行業(yè)靠前的水平為你提供.標(biāo)準(zhǔn)是產(chǎn)品質(zhì)量的保證，主要從事成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、企業(yè)網(wǎng)站建設(shè)、手機(jī)網(wǎng)站制作、網(wǎng)頁設(shè)計(jì)、品牌網(wǎng)站建設(shè)、網(wǎng)頁制作、做網(wǎng)站、建網(wǎng)站。創(chuàng)新互聯(lián)公司擁有實(shí)力堅(jiān)強(qiáng)的技術(shù)研發(fā)團(tuán)隊(duì)及素養(yǎng)的視覺設(shè)計(jì)專才。

兩種集合類的復(fù)雜度分析

在Java底層基于二叉搜索樹實(shí)現(xiàn)集合和映射和Java底層基于鏈表實(shí)現(xiàn)集合和映射中以二分搜索樹和鏈表作為底層實(shí)現(xiàn)了集合Set，在本節(jié)就兩種集合類的復(fù)雜度分析進(jìn)行分析：
測試內(nèi)容：Java底層基于二叉搜索樹實(shí)現(xiàn)集合和映射和Java底層基于鏈表實(shí)現(xiàn)集合和映射中使用的書籍。
測試方法：測試兩種集合類查找單詞所用的時間

 //創(chuàng)建一個測試方法 Set set:他們可以是實(shí)現(xiàn)了該接口的LinkedListSet和BSTSet對象
 private static double testSet(Set set, String filename) {
  //計(jì)算開始時間
  long startTime = System.nanoTime();
  System.out.println("Pride and Prejudice");
  //新建一個ArrayList存放單詞
  ArrayList words1 = new ArrayList<>();
  //通過這個方法將書中所以單詞存入word1中
  FileOperation.readFile(filename, words1);
  System.out.println("Total words : " + words1.size());

  //增強(qiáng)for循環(huán)，定一個字符串word去遍歷words
  //底層的話會把ArrayList words1中的值一個一個的賦值給word
  for (String word : words1)
   set.add(word);//不添加重復(fù)元素
  System.out.println("Total different words : " + set.getSize());

  //計(jì)算結(jié)束時間
  long endTime = System.nanoTime();
  return (endTime - startTime) / 1000000000.0;//納秒為單位
 }

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

 }

結(jié)果：BSTSet的速度比LinkedListed的速度快