Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 算法的复杂性
发信站: 哈工大紫丁香 (2002年03月22日14:37:29 星期五), 站内信件

算法的复杂性
简介
算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高
低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算
法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间
复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追
求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者
，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计
或选用有着重要的指导意义和实用价值。
关于算法的复杂性，有两个问题要弄清楚：
用怎样的一个量来表达一个算法的复杂性；
对于给定的一个算法，怎样具体计算它的复杂性。
让我们从比较两对具体算法的效率开始。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]