本文共 582 字,大约阅读时间需要 1 分钟。
算法是什么?
算法是解决问题的一种方法或者一个过程,更严格的讲,算法是由若干条指令组成的有穷序列,而且满足以下四条性质:
a:输入。参数
b:输出。返回结果
c:确定性。指令语义语法无二义性
d:有限性。执行次数有限
程序是什么?
程序是算法采用某种设计语言的具体实现。程序可以不满足算法的四条性质。
算法的复杂性分析
算法的复杂性是指运行该算法所需要的计算机资源是多少,多则复杂性高,少则复杂性低。对计算机来说,最重要的资源是时间和(存储器)空间。因此算法的复杂性分为时间复杂性和空间复杂性。对于任意给定的问题要尽可能设计复杂性低的算法;对给定问题的多种算法选择发杂性低的算法。时间资源称为时间复杂度,空间资源常委农工委空间复杂度。这两种复杂度表示中都跟问题的规模和算法的输入由密切的关系。复杂度的常用表示由三种,最优情况下的算法复杂度,平均情况下的算法复杂度,最坏情况下的复杂度。实践表明,可操作性最好且最有实际价值的是醉话情况下的复杂度。随着问题的规模的不断扩大,算法的复杂度会出现一个最大的上限和一个最小的下限,采用数学中的夹逼定理可以得到最坏情况下的一个上限近似函数,我们一般选用这个上限函数来表示算法的复杂度。
算法复杂度不但是设计算法时一个可以评估算法的一个工具,也是选取合适算法的一个指导工具。以后介绍的其他算法相关的内容都会用到算法复杂度来衡量。
转载地址:http://srpdi.baihongyu.com/