跳至內容

空七一原理

出自Taiwan Tongues 台語維基
於 2025年8月19日 (二) 22:11 由 TaiwanTonguesApiRobot留言 | 貢獻 所做的修訂 (從 JSON 檔案批量匯入)

(差異) ←上個修訂 | 已批准修訂 (差異) | 最新修訂 (差異) | 下個修訂→ (差異)

空七一原理(空七一 Principle)是由美國史丹福大學出名的電腦教授高德納(Donald Ervin Knuth)提出來的,伊佇咧《電腦程式設計藝術》的第三卷:排序佮選擇中,提出並論證矣這个原理。

空七一原理:如果一个排序網路會當正確來對任何零抹一序列排序,伊就會當對任意陣列做的任意序列正確排序。

這條原理的作用是真大的,為著驗證一个 n 輸入排序網路的正確性,咱毋免檢驗所有的數字構成的任意長為 n 的序列,干焦需要檢驗 $ 二 ^ { n } $ 個零一序列就會當驗證排序網路敢有法度正確來排序。