3．3 模型評(píng)價(jià)
(1)擴(kuò)展性
為層次型有限狀態(tài)機(jī)模型增加新功能，只需在其根節(jié)點(diǎn)下增加一個(gè)子節(jié)點(diǎn)，因?yàn)樾碌淖庸?jié)點(diǎn)與其他兄弟節(jié)點(diǎn)是互斥的，所以模型可以很方便地進(jìn)行系統(tǒng)功能擴(kuò)展。
(2)查找算法時(shí)間復(fù)雜度
假設(shè)系統(tǒng)中存在的狀態(tài)數(shù)量為n。如果不采用層次型有限狀態(tài)機(jī)模型，那么系統(tǒng)中的各個(gè)狀態(tài)都是相互獨(dú)立、互斥的，相當(dāng)于所有的狀態(tài)都是一個(gè)虛擬根節(jié)點(diǎn)的子節(jié)點(diǎn)。這樣的話，查找下一狀態(tài)的時(shí)間復(fù)雜度為：

然而，上面的情況忽略了狀態(tài)之間的相關(guān)性，很有可能當(dāng)前狀態(tài)與下一狀態(tài)是兄弟關(guān)系，此時(shí)的比較次數(shù)就會(huì)明顯減少。如果采用層次型狀態(tài)機(jī)，假設(shè)系統(tǒng)子功能數(shù)目為m(m>1)，那么平均每個(gè)子功能的狀態(tài)數(shù)目為n／m，當(dāng)前狀態(tài)與下一狀態(tài)為兄弟節(jié)點(diǎn)的概率為p(0p1)。這種情況下的時(shí)間復(fù)雜度為：

其中，t1為當(dāng)前狀態(tài)與下一狀態(tài)不是兄弟節(jié)點(diǎn)的查找時(shí)間，與狀態(tài)樹(shù)的平均深度^有關(guān)。但是由于存在局部相關(guān)性，并且這種相關(guān)性越大(即p值越大)，平均時(shí)間復(fù)雜度就越集中在前面部分(p?n)／(m?2)，后面的表達(dá)式值可以忽略不計(jì)，即：

顯然，T(n)2T(n)1。因此，該模型對(duì)于查找下一狀態(tài)在時(shí)間復(fù)雜度上也是有優(yōu)勢(shì)的。

結(jié) 語(yǔ)
通過(guò)建立層次型有限狀態(tài)機(jī)模型，并應(yīng)用改進(jìn)的數(shù)據(jù)結(jié)構(gòu)與狀態(tài)轉(zhuǎn)換算法，自動(dòng)售貨機(jī)控制器的程序結(jié)構(gòu)更為清晰。原來(lái)存在于程序中的諸多標(biāo)志變量，由狀態(tài)機(jī)的各個(gè)狀態(tài)所取代，使系統(tǒng)具有更好的擴(kuò)展性；并且模型很好地利用了狀態(tài)的相關(guān)性，縮短了查找所花費(fèi)的時(shí)間。但是，該模型也存在一定的局限性。比如，很大數(shù)量在構(gòu)造狀態(tài)樹(shù)時(shí)需要的存儲(chǔ)空間給一般嵌入式系統(tǒng)的成本帶來(lái)了挑戰(zhàn)，不過(guò)可以試圖通過(guò)讓所有的狀態(tài)共享內(nèi)存空間的方法來(lái)解決這個(gè)問(wèn)題。因此，層次型有限狀態(tài)機(jī)模型應(yīng)用于較為復(fù)雜的嵌入式系統(tǒng)具有更普遍的意義。