算法合集之用改進(jìn)算法思想解決規(guī)模維數(shù)增大問(wèn)題(編輯修改稿)
2025-07-07 01:38 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 二〗如果我們進(jìn)一步觀察，我們能優(yōu)化上述算法的時(shí)間復(fù)雜度。我們發(fā)現(xiàn)：如果Y不是excellent（因?yàn)橛衂比Y better），當(dāng)我們檢查X是否excellent時(shí)，我們檢查了Z是否比X better的話，可以不檢查Y。因?yàn)槿绻鸜比X better，那么Z一定比X better。然后可以通過(guò)簡(jiǎn)單地修改“改進(jìn)一”。在判斷X是否excellent的時(shí)候，我們只需要在當(dāng)前的excellent選手集合中取得Y即可。主要流程3： for(X從第一次競(jìng)賽的第1名到第一次競(jìng)賽的第N名) for(Y枚舉當(dāng)前已知的excellent) 判斷Y是否比X better這樣，我們能把時(shí)間復(fù)雜度減少到O(NK)（設(shè)K是excellent選手的個(gè)數(shù)）。由于這題K可能很大，算法效果仍然不是很理想?！驹妓悸沸〗Y(jié)】這里的原始算法是直接根據(jù)原始模型模擬出來(lái)的，改進(jìn)一和改進(jìn)二都單純地根據(jù)原始算法的設(shè)計(jì)缺陷來(lái)“改進(jìn)”（這個(gè)改進(jìn)沒(méi)有利用問(wèn)題的特殊性，不是本文所要闡述的“改進(jìn)”），所以最后的時(shí)間復(fù)雜度沒(méi)有質(zhì)的進(jìn)展。【降維思路】本道題規(guī)模還是很明顯的從二維擴(kuò)充到三維。所以還是先用降維的思想，我們先解決選手之間只進(jìn)行兩次競(jìng)賽的問(wèn)題。兩次競(jìng)賽的問(wèn)題同樣可以套用改進(jìn)二的普遍算法。為了方便說(shuō)明，我們?cè)O(shè)第一次競(jìng)賽排名依次為Ai（表示第一次競(jìng)賽的第i名是Ai）， Ai號(hào)選手在第二次競(jìng)賽中的排名的為B[Ai]（注意B[Ai]與Ai的含義不同）。參考“主要流程3”：先是X=A1，顯然A1是excellent；接著X=A2，只需要比較B[A1]與B[A2]大小，不妨假設(shè)B[A2]B[A1]，則A2也是excellent；接下來(lái)，X=A3，我們需要比較B[A1]與B[A3]，B[A2]與B[A3]……假設(shè)A3也是excellent；X=A4時(shí)，我們需要比較B[A1]與B[A4]，B[A2]與B[A4]，B[A3]與B[A4]，假設(shè)A4也是excellent；……。也許這里有心人會(huì)發(fā)現(xiàn)什么，對(duì)了，比較B[A1]與B[X]，B[A2]與B[X]，B[A3]與B[Ai]……的時(shí)候，只要有任何一個(gè)B[Aj]B[Ai](ji)，Ai就不是excellent的，那么，我們只需要用min(B[Aj])與B[Ai]比較！〖改進(jìn)三〗（適用于兩次競(jìng)賽）以上我們看到了一個(gè)特殊的例子：兩次排名完全相反，但是我們可以從中提煉出可行的改進(jìn)算法：對(duì)于兩次競(jìng)賽的情況，當(dāng)X=Ai時(shí)，設(shè)，則B[Ai]只需要與besti比較即可。時(shí)間復(fù)雜度竟然達(dá)到O(N)?！窘稻S思路小結(jié)】在這次分析中，我們從兩次競(jìng)賽——簡(jiǎn)化后的問(wèn)題出發(fā)，通過(guò)簡(jiǎn)單的觀察和思考，得出了改進(jìn)的算法，但是優(yōu)化后的算法要應(yīng)用到三維的情況還有很長(zhǎng)的路要走。【擴(kuò)展思路】我們?cè)鯓影选案倪M(jìn)三”應(yīng)用到三維的情況從而解決問(wèn)題呢？改進(jìn)三的思路能否再明確些？改進(jìn)三的本質(zhì)是什么？其實(shí)，X依照第一次競(jìng)賽的名次循環(huán)，X=Ai時(shí)，因?yàn)橹?，ji這樣就保證了Aj在第一次競(jìng)賽中名次一定比Ai前；如果bestiB[Ai]，這樣就保證了Aj在第二次競(jìng)賽中名次比X前；總之則必然有Aj比Ai better?！几倪M(jìn)四〗能否把改進(jìn)三擴(kuò)展到三次競(jìng)賽上面去呢？為了方便說(shuō)明，我們還需要設(shè)第三次競(jìng)賽中Ai選手名次為C[Ai]。我們假設(shè)這樣一個(gè)過(guò)程：(1)當(dāng)X=Ai，設(shè)ji，則可以保證Aj在第一次競(jìng)賽中名次比Ai前，若不存在這樣的j，則Ai是excellent；(2)在符合(1)條件的所有Aj中找出能滿足B[Aj]B[Ai]的選手，保證Aj在第二次競(jìng)賽中名次比Ai前，若不存在這樣的j，則Ai是excellent；(3)在符合(1)(2)條件的所有Aj中找出min(C[Aj])，比較min(C[Aj])與C[Ai]，若min(C[Aj])C[Ai]，則保證Aj在第三次競(jìng)賽中名次比Ai前，則必有Aj比Ai better，Ai必不是excellent；反之Ai是excellent。以上三個(gè)條件即為：“Ai是excellent”等價(jià)于“不存在這樣的，使”。〖改進(jìn)五〗顯然，如果我們?nèi)匀挥妹杜e的方法來(lái)實(shí)現(xiàn)第(2)步，則最終的算法復(fù)雜度仍然是O(N2)。為什么我們卻說(shuō)這是改進(jìn)過(guò)后的算法呢？因?yàn)槲覀儗?shí)際上利用問(wèn)題的特殊性，改進(jìn)二是純粹的枚舉，進(jìn)行的第(1)步以后要第二第三次競(jìng)賽同時(shí)比較，實(shí)現(xiàn)起來(lái)是很難優(yōu)化的。但是改進(jìn)四則體現(xiàn)了第二第三次競(jìng)賽分步選取的思路，利用這一點(diǎn)能否在實(shí)現(xiàn)中改進(jìn)算法的復(fù)雜度呢？我們可以比較，改進(jìn)二和改進(jìn)四是不同的，在進(jìn)行了第(1)步以后，改進(jìn)二需要同時(shí)考慮第二第三次競(jìng)賽成績(jī)，兩次成績(jī)同時(shí)考慮并不是嚴(yán)格有序的，有時(shí)候我們不能比較二元組(B[Ai],C[Ai])與(B[Aj],C[Aj])的大小（例如當(dāng)B[Ai]B[Aj]，但C[Ai]C[Aj]時(shí)）。而改進(jìn)四的第(2)步可以先考慮第二次競(jìng)賽的成績(jī)，如果我們把第二次競(jìng)賽的成績(jī)用有序數(shù)列來(lái)記錄（設(shè)這個(gè)序列為Dk，即把B[Aj](ji)從小到大排序），我們能輕易找到符合條件的Aj?！几倪M(jìn)六〗由改進(jìn)五可以知道，我們單單從改進(jìn)第(2)步，時(shí)間復(fù)雜度仍然不理想的，能否切實(shí)把第(2)步和第(3)步結(jié)合起來(lái)？經(jīng)過(guò)了改進(jìn)五的改進(jìn)，我們把查找到的符合B[Aj]B[Ai](ji)的Aj在一個(gè)有序數(shù)列中記錄下來(lái)，這樣，符合條件的Aj必然在數(shù)列中是連續(xù)的，設(shè)它是從D1到DK。為了讓第(3)步與第(2)步結(jié)合，我們?cè)僭O(shè)另一個(gè)數(shù)列Ek，使它和Dk一一對(duì)應(yīng)，即Dk與Ek分別代表同一選手在第二第三次競(jìng)賽的名次。這樣，第(3)步又可以簡(jiǎn)化為在一段數(shù)列Ek中查找最小值，即找能否在最短時(shí)間內(nèi)查找出這個(gè)最小值呢？我們需要一種優(yōu)化的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄Dk和Ek。該數(shù)據(jù)結(jié)構(gòu)能很快處理Dk和Ek，并且需要支持兩種操作。插入：加入一對(duì)數(shù)(key,value)到數(shù)據(jù)結(jié)構(gòu)中。查詢：查詢key小于X的最小的value顯然，這里的key代表Dk，val
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1