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

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

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

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

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

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

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

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

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

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

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

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

   

O(n^3)

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

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;

}

這個(gè)算法是絕對(duì)正確的。但是效率非常低下。演示如下：

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

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

我們從上圖看到，其實(shí)FOR2和FOR3都可以進(jìn)行這種篩選最大子序列的操作，因?yàn)樗麄兊男羞M(jìn)軌跡其實(shí)都是一樣的。于是或許可以刪掉那一個(gè)多余的循環(huán)。

   

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;

}

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

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

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

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

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

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

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

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

   

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;

}

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

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

標(biāo)題名稱：數(shù)據(jù)結(jié)構(gòu)如何將復(fù)雜度從O(n^3)殺到O(n)
文章來(lái)源：http://aaarwkj.com/article12/ipdjgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷推廣、虛擬主機(jī)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)