零嗒一原理
外觀
零嗒一原理(零嗒一 Principle)係由米國史丹福大學有名个電腦教授高德納(Donald Ervin Knuth)提出來个,佢在《電腦程式設計藝術》个第三卷:排序同選擇中,並論證了這個原理。
零嗒一原理:係講一個排序个網路做得正確个對任何零法一序列个排序,該恁呢佢就做得對儘採陣列做个儘採序列做正確。
這條原理个作用係蓋大个,為著愛驗證一個 n 輸入著排序網路个正確性,𠊎兜毋使檢驗所有个數字構成个隨意長為 n 个序列,還過淨需要檢驗 $ 二 ^ { n } $ 個零嗒一序列就做得驗證排序網路係毋係做得正確排放序了。