算法合集之動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化-資料下載頁(yè)
2025-10-07 20:30本頁(yè)面
【正文】 章用 L[1..M]表示 ， 則狀態(tài)表示描述為： F(v,i)：表示將 L的前 i個(gè)字符劃分為以動(dòng)詞結(jié)尾 （ 當(dāng) iM時(shí) ， 可帶任意個(gè)輔詞后綴 ） 的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)； F(u,i)：表示將 L的前 i個(gè)字符劃分為以名詞結(jié)尾 （ 當(dāng) iM時(shí) ， 可帶任意個(gè)輔詞后綴 ） 的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù) 。 狀態(tài)轉(zhuǎn)移方程為： F(v,i)=min{ F(u,j)+(0,1)， L(j+1..i)為動(dòng)詞； F(v,j)+(0,1)， L(j+1..i)為輔詞 ， iM； } F(u,i)=min{ F(u,j)+(1,1), L(j+1..i)為名詞； F(v,j)+(0,1), L(j+1..i)為名詞； F(u,j)+(0,1), L(j+1..i)為輔詞 ， iM； } 邊界條件： F(v,0)=(1,0)； F(u,0)=(∞, ∞)； 問(wèn)題的解為： min{ F(v,M), F(u,M) }； 順序查找 二分查找 哈希表 檢索樹(shù) 算法的時(shí)間復(fù)雜度 O(20*M*N) O(20*M*log2N) O(20*M) O(M) 最壞情況下的比較次數(shù) 108 106 105 5*103 超時(shí) 超時(shí) Back 采用不同的方法查找字符串的比較： 設(shè)單詞表的規(guī)模為 N（ N的最大值為 1000） 設(shè)文章的長(zhǎng)度為 M（ M的最大值為 5000） （測(cè)試環(huán)境： Pentium 200 / 32MB）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1