條件：1K內(nèi)存，1MHzCPU，每秒可以改變2^20次狀態(tài)。問：一個程序最長的運行時間是多少？
答： 首先程序是確定性的，就說明內(nèi)存的狀態(tài)不會重復(fù)，否則就永遠結(jié)束不了。從這一點出發(fā)，可以知道內(nèi)存的狀態(tài)共有 2^8k , 然后CPU每秒改變 2^20 個狀態(tài)，所以這臺計算機最長出現(xiàn)不重復(fù)的狀態(tài) 2^(8k-20）秒。 |
posted on 2009-10-15 10:57
尹東斐 閱讀(3705)
評論(12) 編輯 收藏 引用