算法(Algorithm)
使用教材:《算法导论(Introduction to Algorithms)》Third Edition
使用语言:C++
算法是一种技术,是任何良定义(well-defined)的计算过程,是求解良说明的计算问题的工具。所谓well-defined就是指没有歧义(ambiguity)的定义方式。
算法之于计算问题类似于系统之于信号传输,是由输入到输出的中间过程。输入是问题实例(instance),问题陈述中给定了待处理数据和各种约束条件,算法则描述一个特定的计算过程,经此计算过程来得到期望的输出。
这样,算法就是把输入转换成输出的计算步骤的一个序列。
若对于每个输入实例,算法都以正确的输出停机,则称该算法是正确的,并称算法解决了给定的计算问题。而不正确的算法对某些输入实例可能根本不停机,也可能以不正确的输出停机。不正确的算法只有错误率可控时是可用的,但一般使用正确的算法。
如果计算机的算力无限大,存储设备的容量也无限大,那么解决问题的过程中将没有算法什么事情,无论是好的算法还是差的算法,都能在一瞬间解决问题,且占用的存储空间忽略不计。但是,计算机的算力有限,存储器的容量也有限,所以我们一定用到算法,且算法必然有好差之分。
几乎所有问题的解决都有算法的影子,而算法问题有两个共有特征:
1.存在许多候选解,但绝大多数解不能彻底解决问题,所以往往需要寻求一个真正的解或者最好的解;
2.存在实际应用。
计算公式、库函数的使用等等,都有相关文档可查,但算法知识是实实在在的,是否具有算法知识与技术的坚实基础是区分真正熟练的程序员与初学者的一个特征。