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

循环队列的复杂度分析

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

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

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

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

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

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

import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
    private static double testQueue(Queue 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 arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue 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。

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

源码下载

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

导航目录

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

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(2.7)数组队列和循环队列的比较

Leave a Reply

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

立即加入 了解更多