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

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

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

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

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