最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(6.3) 集合类的复杂度分析

    集合类的复杂度分析

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

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

    代码演示

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

    import java.util.ArrayList;
    
    public class Main {
    
        private static double testSet(Set set, String filename){
    
            long startTime = System.nanoTime();
    
            System.out.println(filename);
            ArrayList 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 bstSet = new BSTSet<>();
            double time1 = testSet(bstSet, filename);
            System.out.println("BST Set: " + time1 + " s");
    
            System.out.println();
    
            LinkedListSet 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这些数据,可以创建如下两个二分搜素树,右边的二分搜素树每一个节点的左孩子都为空,只有右孩子。

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

    集合的时间复杂度总结

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

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(6.3) 集合类的复杂度分析

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 159会员总数(位)
    • 3736资源总数(个)
    • 1本周发布(个)
    • 0 今日发布(个)
    • 405稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级