java中什么情況下不能使用最壞情況評(píng)估算法的復(fù)雜度

小編給大家分享一下java中什么情況下不能使用最壞情況評(píng)估算法的復(fù)雜度，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

動(dòng)態(tài)數(shù)組

動(dòng)態(tài)數(shù)組，對(duì)應(yīng)于Java中的ArrayList，在插入元素時(shí)，分成兩種情況：

1. 數(shù)組未滿，元素放在size下標(biāo)的位置即可；

2. 數(shù)組滿了，需要擴(kuò)容，一般擴(kuò)容為N倍大小，Java里面是1.5倍，擴(kuò)容時(shí)需要?jiǎng)?chuàng)建一個(gè)新的數(shù)組，并把原來(lái)的元素一個(gè)一個(gè)地拷貝到新的數(shù)組中，再插入新的元素；

我簡(jiǎn)單地寫(xiě)一段代碼，你可以感受下：

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

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

    // 插入元素，時(shí)間復(fù)雜度為多少呢？
    public void add(int element) {
        // 判斷是否需要擴(kuò)容
        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);
        }
    }
}

那么，對(duì)于動(dòng)態(tài)數(shù)組，它的插入元素方法的時(shí)間復(fù)雜度是多少呢？

按照上一節(jié)的說(shuō)法，按照最壞情況來(lái)評(píng)估，最壞情況是插入元素時(shí)正好數(shù)組滿了需要擴(kuò)容的時(shí)候，此時(shí)，需要?jiǎng)?chuàng)建一個(gè)額外的數(shù)組，同時(shí)有一個(gè)遍歷原數(shù)組的過(guò)程。

所以，在最壞情況下，動(dòng)態(tài)數(shù)組插入元素的時(shí)間復(fù)雜度為O(n)。

但是，這樣合理嗎？

顯然是不合理的，我插入前面(n-1)個(gè)元素的時(shí)候，它的時(shí)間復(fù)雜度都是O(1)，就只有插入第n個(gè)元素的時(shí)候它的時(shí)間復(fù)雜度才是O(n)，所以，這樣來(lái)評(píng)估動(dòng)態(tài)數(shù)組插入元素的時(shí)間復(fù)雜度明顯不合理。

那么，如果我把第n個(gè)元素插入所需要的時(shí)間均攤到所有元素上會(huì)怎么樣呢？

這樣的話，前面每個(gè)元素的插入時(shí)間只需要加1，變成O(2)，忽略常數(shù)項(xiàng)，就還是O(1)，這樣明顯是要合理一些。

這種方式跟計(jì)算平均時(shí)間復(fù)雜度有點(diǎn)類(lèi)似，但是，它不是平均時(shí)間復(fù)雜度，它有一個(gè)專門(mén)的名稱叫做均攤時(shí)間復(fù)雜度。

均攤時(shí)間復(fù)雜度，即對(duì)一批樣本中出現(xiàn)的個(gè)例情況，將它們耗費(fèi)的時(shí)間均攤到所有樣本上，算出來(lái)的一個(gè)時(shí)間復(fù)雜度。

你可以把它和平均時(shí)間復(fù)雜度對(duì)比一下：

1. 平均時(shí)間復(fù)雜度的計(jì)算中沒(méi)有個(gè)例，所有樣本是同等看待的，想一下線性查找的過(guò)程；

2. 均攤時(shí)間復(fù)雜度的計(jì)算中有個(gè)例，這種個(gè)例往往就是最壞的情況，想一下動(dòng)態(tài)數(shù)組插入元素的過(guò)程；

3. 線性查找第n個(gè)元素不是個(gè)例，不能把它的時(shí)間均攤到所有元素上；

這兩個(gè)概念嚴(yán)格來(lái)說(shuō)是有區(qū)別的，如果無(wú)法理解，當(dāng)成一樣的也問(wèn)題不大，比如，這里如果按平均時(shí)間復(fù)雜度計(jì)算的話，結(jié)果為 (1+1+1+...+n)/n = (n-1+n)/n = (2n-1)/n=2-1/n，忽略常數(shù)項(xiàng)和低階項(xiàng)，最終的結(jié)果也是O(1)。

好了，那么，我們?cè)賮?lái)看一下動(dòng)態(tài)數(shù)組插入元素時(shí)的額外空間復(fù)雜度。

是不是一樣的道理？數(shù)組未滿時(shí)額外空間復(fù)雜度為O(1)，數(shù)組滿時(shí)額外空間復(fù)雜度為O(n)，均攤一下變成O(1)。

所以，對(duì)于動(dòng)態(tài)數(shù)組插入元素的過(guò)程，它的均攤時(shí)間復(fù)雜度和均攤額外空間復(fù)雜度都是O(1)。

快速排序

大家都知道經(jīng)典的快速排序的時(shí)間復(fù)雜度是O(nlogn)，那么，它的最壞時(shí)間復(fù)雜度是不是也是O(nlogn)呢？

讓我們來(lái)看下面這個(gè)數(shù)組：

這是一個(gè)有序數(shù)組，如果此時(shí)用經(jīng)典快速排序來(lái)對(duì)其進(jìn)行排序會(huì)怎樣呢？

我們?nèi)∽钣疫叺脑貫檩S（Pivot），也就是12，將小于12的放在它的左邊，大于12的放在它的右邊，發(fā)現(xiàn)沒(méi)有比12大的，所以，右邊沒(méi)有元素，經(jīng)過(guò)此步，12的位置固定不變了。

接著，將12左右兩邊的元素再各取最右邊的元素為軸，12的右邊沒(méi)有元素，所以，只需要處理左邊就可以了，以10為軸，比10小的放在它的左邊，比10大的放在它的右邊，發(fā)現(xiàn)10的右邊也沒(méi)有元素（12已經(jīng)固定了），經(jīng)過(guò)此步，10的位置固定了。

同樣地，最后一步到1這里，排序完成。

讓我們來(lái)分析一下整個(gè)過(guò)程的復(fù)雜度：

第一步，需要遍歷(n-1)個(gè)元素；

第二步，需要遍歷(n-2)個(gè)元素；

...

最后一步，需要遍歷0個(gè)元素；

這種情況下的時(shí)間復(fù)雜度為：(n-1) + (n-2) + ... + 1 + 0 = (n-1)n/2 = n^2/2 - n/2，忽略常數(shù)項(xiàng)和低階項(xiàng)，它的時(shí)間復(fù)雜度為O(n^2)。

所以，對(duì)于有序數(shù)組，使用經(jīng)典快速排序，它的時(shí)間復(fù)雜度為O(n^2)，這也是最壞的情況。

但是，似乎從來(lái)沒(méi)有人告訴你，經(jīng)典快速排序的時(shí)間復(fù)雜度為O(n^2)，而是O(nlog2)，這是為什么呢？

那是因?yàn)橛行驍?shù)組相對(duì)于經(jīng)典快速排序，也是屬于個(gè)例，窮舉無(wú)限多的樣本之后，有序數(shù)組的可能性實(shí)在是太小，所以，我們一般說(shuō)經(jīng)典快速排序的時(shí)間復(fù)雜度為O(nlogn)，而不是以最壞情況來(lái)評(píng)估它的時(shí)間復(fù)雜度。

以上是“java中什么情況下不能使用最壞情況評(píng)估算法的復(fù)雜度”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！