此條目沒有列出任何參考或來源。 (2012年12月25日) 維基百科所有的內容都應該可供查證。請協助補充可靠來源以改善這篇條目。無法查證的內容可能會因為異議提出而被移除。 |
0-1原理(0-1 Principle)是由美國斯坦福大學著名的計算機教授高德納(Donald Ervin Knuth)提出來的,他在《計算機程序設計藝術》的第三卷:排序與選擇中,提出並論證了這個原理。
0-1原理:如果一個排序網絡能夠正確地對任何0-1序列排序,那麼它就能對任意數組成的任意序列正確排序。
這條原理的作用是很大的,為了驗證一個n輸入排序網絡的正確性,我們不必檢驗所有數字構成的任意長為n的序列,而只需檢驗 個0-1序列就足以驗證排序網絡是否能正確排序了。