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中什么情況下不能使用最壞情況評估算法的復雜度”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！