Algorithm: Core Concepts

20th August 2020 at 2:19pm
Algorithm

Algorithms (Jeff Erickson) 对算法给的定义是:

An algorithm is an explicit, precise, unambiguous, mechanically-executable sequence of elementary instructions, usually intended to accomplish a specific purpose.

比如要计算两个数字相乘。问题本身包含了输入及预期的输出,算法则是用来表达输入如何变成输出的过程。

输入:存在两个数组 X[0..m1]X[0..m-1]Y[0..n1]Y[0..n-1] 用来表示数字。

x=i=0m1X[i]10ix = \displaystyle\sum_{i=0}^{m-1}X[i] \cdot 10^i and y=j=0n1Y[j]10jy = \displaystyle\sum_{j=0}^{n-1}Y[j] \cdot 10^j

输出:得到数组 Z[0..m+n1]Z[0..m+n-1],表示相乘结果。

算法:用加法和单个数字的乘法来计算:

xy=i=0m1j=0n1(X[i]Y[j]10i+j)x \cdot y = \displaystyle\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}(X[i] \cdot Y[j] \cdot 10^{i+j})

上面是精确的数学公式表达。也可以用类似计算机伪码的方表达:

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]

这几个算法的时间复杂度都是 O(mn)O(mn),因为计算量取决于单个数字相乘的次数。