跳转到内容

计算资源

维基百科,自由的百科全书

计算复杂性理论中,计算资源是一些计算模型在解决计算问题时使用的资源。

最简单的计算资源是计算时间,即解决一个问题所需的步骤数,以及内存空间,即解决问题时需要的存储量,但也有许多更复杂的资源被定义。  [需要引用]

一个计算问题一般[引用]是以其对任何有效输入的行动来定义的。问题的例子可能是 "给定一个整数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).