Control 版 (精华区)

发信人: doer (老三： 醉亦何妨), 信区: Control
标  题: 算法复杂性1(转载)
发信站: 哈工大紫丁香 (2002年06月08日10:41:04 星期六), 转信

【 以下文字转载自 Algorithm 讨论区 】
【 原文由 longforyou 所发表 】

  简介
算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低
体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的
复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 

计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复
杂性和空间复杂性之分。 

不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求
的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是
我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用
有着重要的指导意义和实用价值。 

关于算法的复杂性，有两个问题要弄清楚： 

用怎样的一个量来表达一个算法的复杂性； 
对于给定的一个算法，怎样具体计算它的复杂性。 
让我们从比较两对具体算法的效率开始



--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 61.156.24.116]
※ 修改:·Lerry 於 06月07日20:20:38 修改本文·[FROM: FTCL.hit.edu.cn]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shao.hit.edu.cn]