算法合集之多串匹配算法及其啟示-資料下載頁
2024-10-18 18:36本頁面
【正文】 “ e” a b c b c d 6 5 3 9 1 2 4 7 8 d e 編號(hào) 1 2 3 4 5 6 7 8 9 Shift 4 3 2 1 1 3 2 1 4 P P P P 找到匹配“ abcd” 找到匹配“ bcde” 主算法二（續(xù)） ?時(shí)間復(fù)雜度分析： ? 設(shè)最短的模式串長度為 θ ? 最壞情況 O(N) ? 設(shè)所有的模式串長度均為 θ， θ足夠大時(shí)，若正文隨機(jī)。 ? ScanB將所有的 T[Left+1..Right]的字符掃描完畢的概率并不大，可以證明平均復(fù)雜度： )log( 26???nO算法總結(jié) ——啟示 1 ? 的使用 ? 變大 —— ? ScanA將很難退出，平均復(fù)雜度變大！ ? 變小 —— ? RightLeft的差變小， ScanB的 pos回到 Left+1的可能性變大，平均復(fù)雜度變大！ 2?32?3?中間值！ 算法總結(jié) ——啟示 2 ?優(yōu)劣得所的思想 ?算術(shù)平均數(shù) —— 本算法 ?幾何平均數(shù) —— Editor塊狀鏈表 ? 不斷更新的數(shù)組 A[1..10000]，求max{A[1..i]} ? 更新： O(10000)。取值： O(1) ? 二叉樹（不易實(shí)現(xiàn)） ? max1[i]記錄 A[1*100~(i1)*100]中的最大值 ? 更新： O(100)。取值： O(100) 啟示 ?一條鐵鏈的強(qiáng)度，決定于最弱的鐵環(huán)的強(qiáng)度 一個(gè)水桶的水量，決定于最短的竹片的長度 ?在算法 深度 達(dá)到一定程度的前提下，我們應(yīng)該將算法的 廣度 拓寬， 多種算法 并用，從 最弱的點(diǎn) 找到解決問題的鑰匙。 ?只要不斷地從 瓶頸 處突破，解題將會(huì)“有山就有路，有河就能渡”！ ?最重要的是領(lǐng)悟“ 融會(huì)貫通 ”的思想 That’s all! Thank you for listening.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1