算法合集之《回到起點(diǎn)——一種突破性思維》-預(yù)覽頁
【正文】 法 ?O(n3) 問題一的解決 —— 另類算法 ?O(n3) ?優(yōu)點(diǎn)： ?極易實(shí)現(xiàn) ?啟發(fā)性強(qiáng)（有潛力可挖） ? 尋找冗余！ ?這一段的檢索有必要嗎？ 問題一的解決 —— 另類算法 …… …… ? 對已覆蓋的區(qū)間，新增后續(xù)指針 ?走進(jìn)已覆蓋離散格時(shí)，沿指針進(jìn)入下一個(gè)離散格 ?將途徑離散格的后續(xù)指針設(shè)為當(dāng)前覆蓋區(qū)間之后的第一格。 i ti 最優(yōu) z序列 注：為了更清楚地說明諸引理與算法，下文將多次出現(xiàn)類似的圖。 ? z序列組成的方案可用 (z1,z2,… zn)表示。 問題二的解決 —— 第一類算法 ? 方法一：平衡二叉樹 O(n(logn)2) ? 方法二：最大堆 O(n(logn)2) – 可以嚴(yán)密證明，區(qū)間合并時(shí)相鄰兩個(gè)區(qū)間的數(shù)，最大一半的并集，恰好是合并后區(qū)間最大的一半 ? 方法三：在方法二基礎(chǔ)上尋找冗余，努力避免集合的合并操作 O(nlogn) ? 方法四：左偏樹 O(nlogn) ? 實(shí)現(xiàn)難！思考深度大！ 問題二的解決 —— 引理 ? 對給定的 t序列 t[1..n]，如果 z[1..n]是一組最優(yōu)策略，那么我們可以假定： ? 滿足 z[i]x的最小的 i，恰好是最小的 i使得對任意 i≤j≤n ， t[i..j]的中位數(shù) x。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1