算法合集之用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題-資料下載頁(yè)
2024-10-18 18:37本頁(yè)面
【正文】 【擴(kuò)展思路】 X依照第一次競(jìng)賽的名次循環(huán)， X=Ai時(shí)，因?yàn)?besti=min(B[Aj])(ji)中， ji， 這樣就保證了 Aj在第一次競(jìng)賽中名次一定比 Ai前； 如果 bestiB[Ai]， 這樣就保證了 Aj在第二次競(jìng)賽中名次比 X前； 總之則必然有 Aj比 Ai better。 【例題】 Team Selection (Balkan OI 2021 Day1) 改進(jìn)三本質(zhì)： [Aj]B[Ai] i min(C[Aj]) 和 C[Ai]（ C表示第三次競(jìng)賽排名） Ai是 excellent 等價(jià)于 ][])[m in ( ij ACAC ?]}[][,|{ ij ABABijjj ???不存在這樣的 j 〖改進(jìn)四 〗 【擴(kuò)展思路】 【例題】 Team Selection (Balkan OI 2021 Day1) 〖改進(jìn)五 〗 通過(guò)改進(jìn)四，我們觀察到，我們要在一個(gè)數(shù)列中找 B小于某個(gè)數(shù)的元素，又要找出所有這些元素的 C的最小值。 【例題】 Team Selection (Balkan OI 2021 Day1) 【擴(kuò)展思路】 也就是說(shuō)，我們需要做這樣的操作： 插入：加入一對(duì)數(shù) (key,value)到數(shù)據(jù)結(jié)構(gòu)中。 查詢：查詢 key小于 X的最小的 value 顯然，這里的 key代表 B[Ai]， value代表 C[Ai]。 【改進(jìn)五的實(shí)現(xiàn)：優(yōu)化數(shù)據(jù)結(jié)構(gòu)】 (1,8) (1,4) (5,8) (1,2) (3,4) 1 2 4 3 ………… 我們構(gòu)建如圖的數(shù)據(jù)結(jié)構(gòu)，也就是二叉檢索樹，每個(gè)節(jié)點(diǎn)表示某一個(gè) key的區(qū)間，節(jié)點(diǎn)的值是該區(qū)間內(nèi)value的最小值。 在這樣的數(shù)據(jù)結(jié)構(gòu)的幫助下，插入和查詢操作都能在 O(LogN)的時(shí)間復(fù)雜度下完成。 【例題】 Team Selection (Balkan OI 2021 Day1) 〖 最終算法 〗 這樣我們就能很清晰地得出優(yōu)化的解法：以第一次競(jìng)賽的名次從高到低枚舉 X， 以第二次競(jìng)賽名次為 key， 第三次競(jìng)賽名次為 value。 對(duì)于每個(gè) X，只要查詢區(qū)間 [1,key]的最小值 minvalue， 若 minvaluevalue， 則有選手比 X better， 即 X 不是excellent。 反之 ， 若 minvaluevalue， 說(shuō)明 X是excellent， 并把 (key,value)加入檢索樹 。 【例題】 Team Selection (Balkan OI 2021 Day1) Time:O(NLogN) 【 小結(jié) 】 Team Selection 一 題不僅很好地反映了改進(jìn)算法對(duì)解決規(guī)模維數(shù)增大的問(wèn)題所起的重要作用 ， 而且還突出了數(shù)據(jù)結(jié)構(gòu)的應(yīng)用對(duì)解決問(wèn)題的幫助 。 正是印證了“ 算法 +數(shù)據(jù)結(jié)構(gòu) =程序 ” 【例題】 Team Selection (Balkan OI 2021 Day1) 四、總結(jié) 改進(jìn)算法的思想究竟是什么呢？ 開闊進(jìn)取的思想：永不滿足于現(xiàn)狀，不斷改進(jìn) 創(chuàng)新的思想：摒棄舊思維，創(chuàng)造新思維 希望大家不僅在程序設(shè)計(jì)中不斷進(jìn)取和創(chuàng)新，在人生中也要有不斷進(jìn)取和創(chuàng)新。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1