专栏首页彤哥读源码什么情况下不能使用最坏情况评估算法的复杂度?

什么情况下不能使用最坏情况评估算法的复杂度?

关注公众号“彤哥读源码”,解锁更多源码、基础、架构知识!

前言

你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。

上一节,我们从最坏、平均、最好三种情况分析了算法的复杂度,得出结论,通常来说,使用最坏情况来评估算法的复杂度完全够用了。

但是,有些算法是不能使用最坏情况来评估算法的复杂度的。

那么,有哪些算法呢?

本节,我们将从动态数组以及快速排序这两个个例入手来分析不能使用最坏情况评估复杂度的情形。

动态数组

动态数组,对应于Java中的ArrayList,在插入元素时,分成两种情况:

  1. 数组未满,元素放在size下标的位置即可;
  2. 数组满了,需要扩容,一般扩容为N倍大小,Java里面是1.5倍,扩容时需要创建一个新的数组,并把原来的元素一个一个地拷贝到新的数组中,再插入新的元素;

我简单地写一段代码,你可以感受下:

public class DynamicArray {
    private int[] array;
    private int size;

    public DynamicArray(int capacity) {
        this.array = new int[capacity];
        this.size = 0;
    }

    // 插入元素,时间复杂度为多少呢?
    public void add(int element) {
        // 判断是否需要扩容
        if (size >= array.length) {
            int newCapacity = array.length + (array.length >> 1);
            int[] newArray = new int[newCapacity];
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            this.array = newArray;
        }
        array[size++] = element;
    }

    public int[] getArray() {
        return array;
    }

    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray(4);
        dynamicArray.add(1);
        dynamicArray.add(2);
        dynamicArray.add(3);
        dynamicArray.add(4);
        dynamicArray.add(5);
        dynamicArray.add(6);

        for (int element : dynamicArray.getArray()) {
            System.out.println(element);
        }
    }
}

那么,对于动态数组,它的插入元素方法的时间复杂度是多少呢?

按照上一节的说法,按照最坏情况来评估,最坏情况是插入元素时正好数组满了需要扩容的时候,此时,需要创建一个额外的数组,同时有一个遍历原数组的过程。

所以,在最坏情况下,动态数组插入元素的时间复杂度为O(n)。

但是,这样合理吗?

显然是不合理的,我插入前面(n-1)个元素的时候,它的时间复杂度都是O(1),就只有插入第n个元素的时候它的时间复杂度才是O(n),所以,这样来评估动态数组插入元素的时间复杂度明显不合理。

那么,如果我把第n个元素插入所需要的时间均摊到所有元素上会怎么样呢?

这样的话,前面每个元素的插入时间只需要加1,变成O(2),忽略常数项,就还是O(1),这样明显是要合理一些。

这种方式跟计算平均时间复杂度有点类似,但是,它不是平均时间复杂度,它有一个专门的名称叫做均摊时间复杂度。

均摊时间复杂度,即对一批样本中出现的个例情况,将它们耗费的时间均摊到所有样本上,算出来的一个时间复杂度。

你可以把它和平均时间复杂度对比一下:

  1. 平均时间复杂度的计算中没有个例,所有样本是同等看待的,想一下线性查找的过程;
  2. 均摊时间复杂度的计算中有个例,这种个例往往就是最坏的情况,想一下动态数组插入元素的过程;
  3. 线性查找第n个元素不是个例,不能把它的时间均摊到所有元素上;

这两个概念严格来说是有区别的,如果无法理解,当成一样的也问题不大,比如,这里如果按平均时间复杂度计算的话,结果为 (1+1+1+...+n)/n = (n-1+n)/n = (2n-1)/n=2-1/n,忽略常数项和低阶项,最终的结果也是O(1)。

好了,那么,我们再来看一下动态数组插入元素时的额外空间复杂度。

是不是一样的道理?数组未满时额外空间复杂度为O(1),数组满时额外空间复杂度为O(n),均摊一下变成O(1)。

所以,对于动态数组插入元素的过程,它的均摊时间复杂度和均摊额外空间复杂度都是O(1)。

快速排序

大家都知道经典的快速排序的时间复杂度是O(nlogn),那么,它的最坏时间复杂度是不是也是O(nlogn)呢?

让我们来看下面这个数组:

这是一个有序数组,如果此时用经典快速排序来对其进行排序会怎样呢?

我们取最右边的元素为轴(Pivot),也就是12,将小于12的放在它的左边,大于12的放在它的右边,发现没有比12大的,所以,右边没有元素,经过此步,12的位置固定不变了。

接着,将12左右两边的元素再各取最右边的元素为轴,12的右边没有元素,所以,只需要处理左边就可以了,以10为轴,比10小的放在它的左边,比10大的放在它的右边,发现10的右边也没有元素(12已经固定了),经过此步,10的位置固定了。

同样地,最后一步到1这里,排序完成。

让我们来分析一下整个过程的复杂度:

第一步,需要遍历(n-1)个元素;

第二步,需要遍历(n-2)个元素;

...

最后一步,需要遍历0个元素;

这种情况下的时间复杂度为:(n-1) + (n-2) + ... + 1 + 0 = (n-1)n/2 = n^2/2 - n/2,忽略常数项和低阶项,它的时间复杂度为O(n^2)。

所以,对于有序数组,使用经典快速排序,它的时间复杂度为O(n^2),这也是最坏的情况。

但是,似乎从来没有人告诉你,经典快速排序的时间复杂度为O(n^2),而是O(nlog2),这是为什么呢?

那是因为有序数组相对于经典快速排序,也是属于个例,穷举无限多的样本之后,有序数组的可能性实在是太小,所以,我们一般说经典快速排序的时间复杂度为O(nlogn),而不是以最坏情况来评估它的时间复杂度。

我们这里说的是经典快速排序,为什么要加“经典”两个字呢?

后记

好了,本节,我们通过两个案例来说明了并不是所有的算法都使用最坏情况来评估它的复杂度。

到现在为止,我们都是使用的大O来表示算法的复杂度,但是,在其它书籍中,你可能还见过Θ、Ω等表示法,它们又是什么意思呢?

下一节,我们接着聊。

本文分享自微信公众号 - 彤哥读源码(gh_63d1b83b9e01),作者:丹卿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂度分析的套路及常见的复杂度

    上一节,我们一起学习了表示复杂度的几个符号,我们说,通常使用大O来表示算法的复杂度,不仅合理,而且书写方便。

    彤哥
  • O、Θ、Ω、o、ω,别再傻傻分不清了!

    前面几节,我们一起学习了算法的复杂度如何分析,并从最坏、平均、最好以及不能使用最坏情况全方位无死角的剖析了算法的复杂度,在我们表示复杂度的时候,通常使用大O来表...

    彤哥
  • 到底什么才是真正的空间复杂度?

    现在有一个算法是这样的,给定一个数组,将数组中每个元素都乘以2返回,我实现了下面两种形式:

    彤哥
  • 针对封装数组的简单复杂度分析

    此处的复杂度分析主要是指时间复杂度分析,算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。

    wfaceboss
  • 数据结构算法入门--一文了解什么是复杂度

    最近会开始更新一个数据结构算法的学习系列,同时不定期更新 leetcode 的刷题。

    材ccc
  • 昨天的文章,有朋友给出"更好的"解法,其实并不是...

    昨天推送一道题目分析,一方面学习一个颇具特色的数组,它的取值不大于数组长度;另一方面通过这道题充分体会算法分析、逻辑推理的重要性。只有做好充分的分析,才可能写出...

    double
  • 看动画轻松理解时间复杂度(二)

    上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级,这篇文章来讲讲另外几种复杂度: 递归算法的时间复杂度(recursive algorithm ...

    五分钟学算法
  • 02 复杂度分析_pythoner学习数据结构与算法系列

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度...

    诡途
  • 读张逸的领域驱动设计之应对软件复杂度笔记 原

        Eric Evans认为"很多应用程序最主要的复杂度并不是技术上,而是来自域本身、用户的活动或业务"。最终决定的因素还是因为需求。

    克虏伯
  • 时间复杂度O(n)和空间复杂度

    算法对于敲代码的应该都听过,不管是复杂的还是简单的,衡量算法效率的两个重要指标就是时间复杂度和空间复杂度。

    wade

扫码关注云+社区

领取腾讯云代金券