數據結構如何將復雜度從O(n^3)殺到O(n)

數據結構如何將復雜度從O(n^3)殺到O(n)，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

最近在LEETCODE上剛好做到這一道題(53.Maximum Subarray)。突然想到數據結構中也有這道題目的例子，于是起興來個總結。

題目: 給你一個數組，讓你求出其中最大的子序列之和。

如：輸入[-2,1,-3,4,-1,2,1,-5,4]，其最大的子序列之和為6([4,-1,2,1]).

PS：還記得時間復雜度怎么計算的嗎？

以最壞的情況為基準，數量級至上。嵌套相乘，同級相加。

可能需要說明的函數/定義：

max(a,b) : 返回a,b中較大的那一個。

vector<int>&nums : 傳入一個vector庫，若你對它很陌生，可以暫時把它看做數組(當然它和數組有區別)。

以下所有代碼均只有函數部分。

完整代碼可在: https://github.com/Ckend/GongZhongHao/tree/master/2.27 中查看。

   

O(n^3)

首先，最直接的思維是將每一個子序列的和都求出來。temp的作用是：1.求每個子序列的和，2.每次求完都會和result對比，如果比result大，則將值賦給result。每次這兩個操作結束，temp都會清零。

int MaxSubSequenceSum(std::vector<int>&nums){

    int temp = 0 , result = 0;

    for (int i = 0 ; i < nums.size(); ++i) {

        for (int j = i; j < nums.size(); ++j) {

            temp = 0;

            for (int k = i; k <= j; ++k) {

                temp += nums[k];

                result = std::max(result, temp);

            }

        }

    }

    return result;

}

這個算法是絕對正確的。但是效率非常低下。演示如下：

演示并未展現出全部的可能（或許也有點不太準確，最后黃色部分不應該和紫色部分共同前進），但是就如同紫色部分，所有的子序列都會被檢測一遍。

我們會思考是否沒必要使用三個循環，也許兩個循環就夠了?

我們從上圖看到，其實FOR2和FOR3都可以進行這種篩選最大子序列的操作，因為他們的行進軌跡其實都是一樣的。于是或許可以刪掉那一個多余的循環。

   

O(n^2)

int MaxSubSequenceSum(std::vector<int>&nums){

    int temp = 0, result = 0;

    for (int i = 0; i < nums.size(); ++i) {

        for (int j = i; j < nums.size(); ++j) {

            temp += nums[j];

            result = std::max(result, temp);

        }

        temp = 0;

    }

    return result;

}

雖然說O(n^2)是一個比較可以接受的復雜度。但是如果我們想要更加優化的算法。可能就要往抽象領域里延伸了。

這個O(n)的算法僅僅七行代碼，但是想要理解清楚可沒那么簡單。我們可以從中看出，它與O(n^2)算法的最大區別在于，少了一個循環，并且temp = 0 被 temp = std::max(0, temp) 代替。

為什么我們在O(n^2)的算法中需要兩次循環？因為我們需要把temp清零以保存下一輪的最大值。但是如果我們舍棄這一步操作呢？當序列中全是正數的時候，毋庸置疑，最大子序列就是它自身，于是我們只需要討論兩種情況：

1.序列中有一個以上的正數

當序列中只有一個正數的時候，自然，子序列就是那一個正數。

當序列有大于兩個正數的時候，我們可以確定，最大子序列一定大于0。所以當temp的合小于零的時候，我們可以確定這條序列絕對不是最大子序列，于是將它清零，否則temp不清零。直到遇到真正的最大子序列。

2.序列中全是負數

如果序列中全是負數，那么最大子序列肯定只有一個數。利用result = std::max(result, temp);可以直接判斷出來。

   

O(n)

int MaxSubSequenceSum(std::vector<int>&nums){

    int temp = 0, result = nums[0];

    for (int i = 0; i < nums.size(); ++i) {

        temp += nums[i];

        result = std::max(result, temp);

        temp = std::max(0, temp);

    }

    return result;

}

于是通過這種巧妙的方法，我們成功實現了將算法復雜度優化到O(n)的目標。如果你還是不太明白，我的經驗是要不斷地歸納總結，總是會有一點收獲的。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。