快捷導(dǎo)航

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

更新時(shí)間：2020年03月29日 13:03:41 作者：WFaceBoss

這篇文章主要介紹了Java基于二分搜索樹(shù)、鏈表的實(shí)現(xiàn)的集合Set復(fù)雜度分析,結(jié)合實(shí)例形式詳細(xì)分析了Java基于二分搜索樹(shù)、鏈表的實(shí)現(xiàn)的集合Set復(fù)雜度分析相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了Java基于二分搜索樹(shù)、鏈表的實(shí)現(xiàn)的集合Set復(fù)雜度分析。分享給大家供大家參考，具體如下：

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

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

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

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

  //計(jì)算結(jié)束時(shí)間
  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("————————————————————");
  //基于鏈表實(shí)現(xiàn)的集合
  LinkedListSet<String> linkedListSet = new LinkedListSet<>();
  double time2 = testSet(linkedListSet, "pride-and-prejudice.txt");
  System.out.println("linkedListSet:" + time2 + "s");

 }

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

集合的時(shí)間復(fù)雜度分析：

1.鏈表情況

2.二叉搜索樹(shù)的情況

在基于二叉搜索樹(shù)的情況下，增加、查詢(xún)、刪除的與二叉搜索樹(shù)的深度有關(guān)，每次操作均為從根節(jié)點(diǎn)到某一一支子樹(shù)的葉子節(jié)點(diǎn)之間進(jìn)行操作，時(shí)間復(fù)雜度為0(h),h表示二叉搜索樹(shù)的高度（層數(shù)）。