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

数据结构笔记总结(2.7)数组队列和循环队列的比较

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

循环队列的复杂度分析

虽然循环队列的实现稍微复杂一些,但是这些是非常值得的。

通过循环队列,出队从O(n)的复杂度变为O(1)的复杂度。

我们知道O(n)的复杂度会比O(1)的慢,但是具体慢多少?

这一节我们用程序来模拟一下,让大家能够更直接的看到二者之间的差距。

数组队列和循环队列的比较

首先编写一个测试用例,比较两个队列的效果有什么不同。

import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
    private static double testQueue(Queue<Integer> q, int opCount){

        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i = 0 ; i < opCount ; i ++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for(int i = 0 ; i < opCount ; i ++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");
    }
}

接下来我们运行一下程序,可以看到,运行之后,很长一段时间都没有打印输出,这是因为计算arrayQueue的时间是非常长的,最终在我电脑上运行的结果如下。

对于十万个操作,也就是我们的队列进行十万次入队和十万次出队操作的话,arrayQueue用了4.8秒左右,而loopQueue用了0.017秒左右,这就是二者间巨大的差距。

而差距主要体现在出队这个操作中,对于arrayQueue,每出一次队,队首后面的元素都要向前挪一位,复杂度O(n),则testQueue方法复杂度为n方,对于loopQueue来说,复杂度为O(1),则testQueue复杂度为n。

这就是我们进行算法和数据结构优化的意义所在,对性能的提升是非常明显的,这些优化也是很有必要的。

源码下载

下载地址

导航目录

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

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

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

客服QQ


QQ:2248886839


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