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

兩種集合類的復(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)集合和映射中使用的書籍。測試方法：測試兩種集合類查找單詞所用的時(shí)間

//創(chuàng)建一個(gè)測試方法 Set<String> set:他們可以是實(shí)現(xiàn)了該接口的LinkedListSet和BSTSet對(duì)象 private static double testSet(Set<String> set, String filename) { //計(jì)算開始時(shí)間 long startTime = System.nanoTime(); System.out.println('Pride and Prejudice'); //新建一個(gè)ArrayList存放單詞 ArrayList<String> words1 = new ArrayList<>(); //通過這個(gè)方法將書中所以單詞存入word1中 FileOperation.readFile(filename, words1); System.out.println('Total words : ' + words1.size()); //增強(qiáng)for循環(huán)，定一個(gè)字符串word去遍歷words //底層的話會(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.二叉搜索樹的情況

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

二叉搜索樹復(fù)雜度如下：

2.1 探究鏈表情況下的n與二叉搜索樹的h的關(guān)系

下面對(duì)n與h關(guān)系進(jìn)行推導(dǎo)：

2.1.1 采用滿二叉樹的情況進(jìn)行分析（最優(yōu)情況）

采用滿二叉樹（每個(gè)節(jié)點(diǎn)都有左右節(jié)點(diǎn)，除了葉子節(jié)點(diǎn)）來進(jìn)行分析的原因?yàn)闈M二叉樹是一種極端情況，如下圖：

從上圖中關(guān)于h層總共有多少個(gè)節(jié)點(diǎn)有如下推導(dǎo)：

假設(shè)節(jié)點(diǎn)個(gè)數(shù)為n個(gè)則有如下關(guān)系：

針對(duì)都是log級(jí)別的關(guān)系，底數(shù)是多少不影響它是log級(jí)別的則有：

2.1.2 單個(gè)孩子情況----二叉搜索樹最壞情況（節(jié)點(diǎn)數(shù)等于其高度）

比如：下面這種二叉搜索樹

對(duì)于這種只有單個(gè)孩子的情況，此時(shí)二叉搜索樹退化成了鏈表，此時(shí)的時(shí)間復(fù)雜度為O(n)。

2.2 兩種集合復(fù)雜度統(tǒng)計(jì)

2.2.1 logn和n的差距

推薦是最好的支持，關(guān)注是最大的鼓勵(lì)。親愛的朋友，很榮幸在園子里遇到您。

本節(jié)涉及的源碼地址為https://github.com/FelixBin/dataStructure/tree/master/src/SetPart

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。