算法合集之回到起點——一種突破性思維-閱讀頁
2024-12-23 11:31本頁面
【正文】 最后一個區(qū)間的 z值較前一個區(qū)間小，根據(jù)引理我們合并這兩個區(qū)間，新的 z值設(shè)定為它們的中位數(shù) i ti 第 1個區(qū)間 第 2個區(qū)間 第 3個區(qū)間 合并，找到新的中位數(shù) 問題二的解決 —— 第一類算法 ? 選取一個優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，它可以高效地完成如下任務(wù)： – 集合合并 – 求出該集合的中位數(shù)。 問題二的解決 —— 第一類算法 ? 方法一：平衡二叉樹 O(n(logn)2) ? 方法二：最大堆 O(n(logn)2) – 可以嚴(yán)密證明，區(qū)間合并時相鄰兩個區(qū)間的數(shù)，最大一半的并集，恰好是合并后區(qū)間最大的一半 ? 方法三：在方法二基礎(chǔ)上尋找冗余，努力避免集合的合并操作 O(nlogn) ? 方法四：左偏樹 O(nlogn) ? 實現(xiàn)難！思考深度大！ 問題二的解決 —— 引理 ? 對給定的 t序列 t[1..n]，如果 z[1..n]是一組最優(yōu)策略，那么我們可以假定： ? 滿足 z[i]x的最小的 i，恰好是最小的 i使得對任意 i≤j≤n ， t[i..j]的中位數(shù) x。 i z[j]x | i=j=n x z[j]=x | 1=ji 問題二的解決 —— 第二類算法 ?二分！ i x O(nlogn) 總結(jié) ? 問題的表示往往比答案更重要，答案不過乃數(shù)學(xué)或?qū)嶒灐?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1