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

網(wǎng)站制作、建網(wǎng)站找專業(yè)網(wǎng)絡(luò)公司創(chuàng)新互聯(lián)建站:定制網(wǎng)站、模板網(wǎng)站、仿站、微信小程序定制開發(fā)、軟件開發(fā)、app軟件開發(fā)等。做網(wǎng)站價格咨詢創(chuàng)新互聯(lián)建站:服務(wù)完善、10年建站、值得信賴!網(wǎng)站制作電話：13518219792

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

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

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

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

以最壞的情況為基準(zhǔn)，數(shù)量級至上。嵌套相乘，同級相加。

可能需要說明的函數(shù)/定義：

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

vector&nums : 傳入一個vector庫，若你對它很陌生，可以暫時把它看做數(shù)組(當(dāng)然它和數(shù)組有區(qū)別)。

以下所有代碼均只有函數(shù)部分。

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

   

O(n^3)

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

int MaxSubSequenceSum(std::vector&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;

}

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

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

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

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

   

O(n^2)

int MaxSubSequenceSum(std::vector&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)是一個比較可以接受的復(fù)雜度。但是如果我們想要更加優(yōu)化的算法。可能就要往抽象領(lǐng)域里延伸了。

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

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

1.序列中有一個以上的正數(shù)

當(dāng)序列中只有一個正數(shù)的時候，自然，子序列就是那一個正數(shù)。

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

2.序列中全是負數(shù)

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

   

O(n)

int MaxSubSequenceSum(std::vector&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;

}

于是通過這種巧妙的方法，我們成功實現(xiàn)了將算法復(fù)雜度優(yōu)化到O(n)的目標(biāo)。如果你還是不太明白，我的經(jīng)驗是要不斷地歸納總結(jié)，總是會有一點收獲的。

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。