未來數學家的挑戰
計算量問題 （註釋）

楊照崑;楊重駿

 
註釋

...1
排序 (Sorting) 的方法很多，但都不能低於 $O(n\log{n})$，讀者可在一般 Database 的書中找到有關 Sorting 的法則。
...2
又稱呈多項式上升，但因一個 n 的多項式之大小，在 n 很大時都為第一項所支配，故可寫成 O(nk)。
...3
並不失去一般性，即若距離不是正整數也可以把它們化成正整數。
...4
在古克的原文中，並沒有 NP-complete, NP-hard 之明確定義。但是由於他的論文，使這種分法顯得很自然。 不過 NP-hard 之定義仍因人而異，不一定同於本文。
...5
本文中之解決，均指一個 O(nk) 計量算的解法。
...6
與情報人員之單線作用相同。一個諜報人員只知道他的頂頭上司及他的第一線下層下屬，其餘的人他都不知道。
...7
A,B,C 表任三城，而 d(A,B),d(B,C),d(C,A) 分別表示 A,B; B,C; C,A 城之距離，則 $d(A,B)\leq d(B,C)+d(C,A)$ 稱為三角不等式。
...8
指 19×19 之棋盤，許多計算機學家都是圍棋高手，中國的算盤與圍棋，好像包含了計算機的開始與終極。
   


最後修改時間: 6/29/2002