計算資源

維基百科,自由的百科全書

計算複雜性理論中,計算資源是一些計算模型在解決計算問題時使用的資源。

最簡單的計算資源是計算時間,即解決一個問題所需的步驟數,以及內存空間,即解決問題時需要的存儲量,但也有許多更複雜的資源被定義。  [需要引用]

一個計算問題一般[引用]是以其對任何有效輸入的行動來定義的。問題的例子可能是 "給定一個整數n,確定n是否是素數",或者 "給定兩個數字x和y,計算積x*y"。隨著輸入越來越大,解決一個問題所需的計算資源也會增加。因此,解決一個問題所需的資源是用漸進分析法來描述的,即把資源確定為輸入的長度或大小的函數。資源的使用經常使用大O符號進行部分量化。

計算資源是有用的,因為我們可以研究哪些問題可以在每一種計算資源的一定量中計算出來。通過這種方式,我們可以確定解決問題的算法是否是最優的,我們可以對算法的效率做出說明。所有能用一定量的某種計算資源解決的計算問題的集合是一個複雜性類,而不同複雜性類之間的關係是複雜性理論中最重要的課題之一。

描述普遍可得的計算設備

"計算資源 "一詞通常被用來描述可訪問的計算設備和軟體。參見公用計算。

計算能力的形式化量化

在正式量化計算能力方面已經有了一些努力。有界圖靈機已經被用來為特定的計算建模,使用狀態轉換的數量和字母大小來量化解決一個特定問題所需的計算努力。[1][2]

參考資料[編輯]

  1. ^ Gregory J., Chaitin. On the Length of Programs for Computing Finite Binary Sequences (PDF). Journal of the ACM (JACM). 1966, 13 (4): 547–569 [2007-09-25]. doi:10.1145/321356.321363. (原始內容 (PDF)存檔於2007-02-05). 
  2. ^ Sow, Daby; Eleftheriadis, Alexandros. Representing Information with Computational Resource Bounds (PDF). Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar. Volume 1: 452–456. 1998 [2007-09-25]. ISBN 0780351487. 10.1109/ACSSC.1998.750904. (原始內容存檔 (PDF)於2017-09-21).