huangyhg

计算复杂度理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源。最常见的资源是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。

复杂度理论和可计算性理论不同，可能性理论的重心在于问题能否解决，不管需要多少资源。

__________________
借用达朗贝尔的名言：前进吧，你会得到信心!
[url="http://www.dimcax.com"]几何尺寸与公差标准[/url]