• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(6.3) 集合类的复杂度分析

极客笔记 Geekerstar 11个月前 (05-18) 360次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

集合类的复杂度分析

前两小节实现了两个不同的集合类,它们基于的底层数据结构不一样,一个是基于二分搜索树的集合类BSTSet,另外一个是基于链表的集合类LinkedListSet。

之前的测试中或多或少应该能发现,基于链表的集合类在我们的测试中明显是慢于基于二叉树的集合类,那么具体慢多少呢?这一小节我们对二者的性能做一个比较。

代码演示

下面我们编写一个测试函数,main函数中编写如下代码

import java.util.ArrayList;

public class Main {

    private static double testSet(Set<String> set, String filename){

        long startTime = System.nanoTime();

        System.out.println(filename);
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile(filename, words)) {
            System.out.println("Total words: " + words.size());

            for (String word : words)
                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) {

        String filename = "pride-and-prejudice.txt";

        BSTSet<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet, filename);
        System.out.println("BST Set: " + time1 + " s");

        System.out.println();

        LinkedListSet<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet, filename);
        System.out.println("Linked List Set: " + time2 + " s");

    }
}

运行结果如下

对于BSTSet很快就运行完了,时间大概是0.66秒,而对于LinkedListSet需要5.25秒,显然使用二分搜索树性能是高于使用链表的,

集合时间的复杂度分析

对于LinkedListSet的添加操作来说,本来在链表中添加一个新的元素只需要O(1)的时间复杂度,直接添加在链表的头结点位置。

但是在链表集合的这个实现中,为了保证我们添加的元素不重复,首先需要扫一遍整个链表来确定我们要添加的这个元素在当前的链表中不存在,也就是我们需要首先查一遍,这个查的过程其实是一个O(n)级别的复杂度,这使得添加操作最终的复杂度是O(n)。对于查和删也同理。

而对于二分搜索树来说,时间复杂度是O(h)级别的,其中h表示二分搜索树的高度,每一次从根节点开始都会向下走一层,整个二分搜索树有多少层,也就是最多高度是多少,那么时间复杂度最多就访问这么多节点。

那么这就有个问题了,LinkedListSet是O(n),BSTSet是O(h),n和h到底是什么关系呢?如果不知道h和n的关系还是比较不出二者的性能谁优谁劣。

这里先分析一种最极端的情况,假设整棵搜索树是一棵满的二叉树,这种情况下,很容易看出:第0层也就是根节点,第一层有两个节点,第二层有四个节点,第三层有八个节点……那么我们可以总结如下规律:

如果h为n,那么我们很容易推出

logn和n的差距

二分搜索树最坏情况

同样的数据可以对应不同的二分搜索树,比如都是1,2,3,4,5,6这些数据,可以创建如下两个二分搜素树,右边的二分搜素树每一个节点的左孩子都为空,只有右孩子。

这种情况下的二分搜素树和链表无异,对于这颗二分搜素树,它的高度等于节点个数,这就是二分搜素树最坏的情况。

集合的时间复杂度总结

综上所述,最坏情况下,二分搜索树还可能退化成链表,这也是二分搜素树的局限性,正因如此我们应该想办法解决这个问题,解决办法就是创建平衡二叉树。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(6.3) 集合类的复杂度分析
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00