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

小编给大家分享一下java中什么情况下不能使用最坏情况评估算法的复杂度，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

动态数组

动态数组，对应于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)，而不是以最坏情况来评估它的时间复杂度。

以上是“java中什么情况下不能使用最坏情况评估算法的复杂度”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！