淺談二分策略的應(yīng)用-文庫(kù)吧
2025-01-13 12:56 本頁(yè)面
【正文】 至（ 2） ? 因?yàn)?x是 隨機(jī)選出 的，由簡(jiǎn)單的概率分析，可得算法的復(fù)雜度期望值為 O(n)。 如果 ip，我們將范圍確定為 S中比 x小的元素，求該范圍內(nèi)第 i個(gè)元素； 如果 i=p，表示第 i小的元素就是 x ip，我們將范圍確定為 大的元素，求該范圍內(nèi)第 p1個(gè)元素； 5/19/2023 7 WinterCamp 2023 小結(jié) ?舉這個(gè)例子，是想說明兩點(diǎn)： ? 第一，二分查找 == logn ? 第二，二分查找 == 平均 ? ?5/19/2023 8 WinterCamp 2023 類型二：二分枚舉 —— 應(yīng)用于退化了的有序序列 ?與類型一中的二分查找相比， 最大的區(qū)別 在于這里的二分在判斷選擇哪一個(gè)部分遞歸調(diào)用時(shí)沒有了 比較運(yùn)算 *。 顯式 有序序列 隱含的退化了的 有序序列 5/19/2023 9 WinterCamp 2023 例二： BTP職業(yè)網(wǎng)球賽 ? [問題描述 ] N（ N≤65536） — 有 N頭奶牛（ N是 2P）參加網(wǎng)球淘汰賽。即 N頭奶牛分成 N/2組，每組兩頭奶牛比賽，決出N/2位勝者；所有勝者繼而分成 N/4組比賽 …… 直至剩下一頭牛是冠軍。 K （ 1≤K≤N1） — 比賽既要講求實(shí)力，又要考慮到運(yùn)氣。每頭奶牛都有一個(gè) BTP排名，恰為 1－ N。如果兩頭奶牛的排名相差大于給定整數(shù) K，則排名靠前的奶?？偸勤A排名靠后的奶牛；否則，雙方都有可能獲勝。 Answer— 現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。并要求你列舉出一個(gè)可能的比賽安排使該奶牛獲勝。 5/19/2023 10 WinterCamp 2023 初步分析 ?由于 N很大，猜想可以通過貪心方法解決。 K+1?1 K+2?2 … … 2K?K 3K+1?2K+1 … … … … 5/19/2023 11 Wint
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1