Question

算法的确定性指的是组成算法的每条

Answer 1

算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。

算法是《数据结构》这门课程中常用的一个概念。算法的定义可以简单表述为：“算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。“任何算法都具有确定性。

即“算法中的每一条指令必须有确定的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。”

在笔者教学实践中，常有学生对算法的确定性表示怀疑。甚至有的学生提出一种反对意见：高级语言几乎都提供了随机函数，如果一个算法调用随机函数那么得到的结果事先是无法预知的，该算法也就不具有确定性。本文通过正反两个方面对这种错误观点加以分析。

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔克莱尼分别于1930年、1934年和1935年提出的递归函数。

阿隆佐邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。