算法合集之多角度思考創(chuàng)造性思維-資料下載頁
2024-10-18 18:36本頁面
【正文】 對于本題的數(shù)據(jù)可以同時超空間和超時間了。 不過這只是很粗略的分析，這些狀態(tài)中有很多是取不到的。 )( 3mO)( 4mO效率分析 把根節(jié)點(diǎn)看做第 0層，葉節(jié)點(diǎn)就是第 n層，對于任意的第 i層， A用戶的個數(shù)最多只有 ，而祖先結(jié)點(diǎn)只有 i個，即 k最大只有 ，把 的后兩維合并成一維，空間復(fù)雜度其實(shí)只有 。 in?2i2 ),( kjif)( 2mO效率分析 再看時間復(fù)雜度，對于第 i層，有 個結(jié)點(diǎn)，每個節(jié)點(diǎn)的狀態(tài)數(shù)是 O(m)的，狀態(tài)轉(zhuǎn)移的復(fù)雜度是 ，所以每層的復(fù)雜度是 。 總共有 n層，所以狀態(tài)轉(zhuǎn)移的時間復(fù)雜度是 。 i2)2( inO ?)( 2mO)( 2 nmO回顧 對收費(fèi)規(guī)則進(jìn)行轉(zhuǎn)化 對時間復(fù)雜度進(jìn)行均攤分析 第二點(diǎn)在樹型動態(tài)規(guī)劃中有著廣泛的運(yùn)用，本題通過粗略的分析會超時，但是仔細(xì)分析之后，發(fā)現(xiàn)時間復(fù)雜度比粗略的分析少了一維 總結(jié) 這 2個例題從不同方面闡述了樹型動態(tài)規(guī)劃的解題方法，如： ? 多維動態(tài)規(guī)劃 ? 兄弟結(jié)點(diǎn)之間通過類似背包的思想進(jìn)行第二次動態(tài)規(guī)劃 ? 對復(fù)雜度的均攤分析 這些方法在比賽中有著廣泛的運(yùn)用 總結(jié) 在此過程中，我認(rèn)識到：面對陌生的問題，一方面要深入分析問題的屬性，挖掘問題的本質(zhì)，另一方面要多角度思考，抓住問題的特殊性，從而創(chuàng)造出正確的解題思路。 不過，這類問題變化繁多，我只是提供了一些解題的方法和思路，拋磚引玉，重要的是平時的不斷積累和總結(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1