Algorithms (Jeff Erickson) 对算法给的定义是:
An algorithm is an explicit, precise, unambiguous, mechanically-executable sequence of elementary instructions, usually intended to accomplish a specific purpose.
比如要计算两个数字相乘。问题本身包含了输入及预期的输出,算法则是用来表达输入如何变成输出的过程。
输入:存在两个数组 和 用来表示数字。
and
输出:得到数组 ,表示相乘结果。
算法:用加法和单个数字的乘法来计算:
上面是精确的数学公式表达。也可以用类似计算机伪码的方表达:
FibonacciMultiply(X [0 .. m − 1], Y [0 .. n − 1]):
hold ← 0
for k ← 0 to n + m − 1
for all i and j such that i + j = k
hold ← hold + X [i] · Y [ j]
Z[k] ← hold mod 10
hold ← bhold/10c
return Z[0 .. m + n − 1]
这几个算法的时间复杂度都是 ,因为计算量取决于单个数字相乘的次数。