“算法” algorithm 跟“方法” method 有什么区别?具体怎么区分?

“算法” algorithm 跟“方法” method 有什么区别?具体怎么区分?

这主要是因为 method 一词在不同学科中具有不同的含义。

Jacobi Method 中的 method 是数学领域的词汇。

在数学上,人们习惯把计算一个问题的步骤(尤其是由个别数学家提出而非广为流传的)称为method,此时 method 和 algorithm 是同义词。其他的例子还有 Newton-Raphson method(牛顿拉夫逊迭代法)、Runge-Kutta Method(龙格-库塔数值积分法)等。当然也有的算法叫 algorithm,比如 Euclidean Algorithm(辗转相除法)。

而在计算机科学中,method是一类algorithm的总称。

在CLRS(《算法导论》)中,有一个很好的例子:求解最大流问题(Maximum Flow Problem)的Ford-Fulkerson Method,其内容是:1、初始化一个零流;2、找增广路进行增广。这里最关键的一点是,只给出了计算最大流的大致流程,但每一个流程如何执行却没有详细的说明。在上面的第二步中,若用 BFS 找增广路,就得到 Edmonds-Karp Algorithm;再改用其他手段找增广路,还可以得到 Dinic, ISAP 等不同的 algorithms. 当然,这些 algorithms都属于 Ford-Fulkerson Method.

也就是说,对于一个给定的 problem(问题),method 是一种解决问题的思路,只需给出一个大致的流程,而具体每一步怎么做可以有很多变化,这个词的粒度比较大。同一 method 下可以包含多个时间和空间复杂度都不同(甚至相差很大)的 algorithm。

而 algorithm 则是要给出每一步的具体步骤,可以方便的转化成计算机代码。这个词的粒度比 method 要细很多,但仍具有一定程度的灵活性,可以包含几个不同时空复杂度的变种。

至于 Monte Carlo algorithm,私以为这个例子不太恰当。因为它并不面向问题(problem-oriented)。私以为,这不是一种算法,而是一种设计算法的思路,凡是符合某一特征的算法均可归为此类。就好像我们说动态规划算法、分治算法等一样,不是指某一个具体的算法,而是一种设计算法的常用技术。

以下是私货:

我个人则倾向于进一步区分 algorithm (算法)和 implementation of an algorithm(算法的实现)这两个术语。implementation 有时也称作 variation(算法的变体)。algorithm 虽然比 method 详细了很多,但并不依赖于计算机程序设计语言,更多的是数学层面的东西;而 implementation 通常需要考虑到编程语言和计算机硬件,精细程度到了代码级。一种 algorithm 可以有多种 implementation,例如求单源最短路径的Dijkstra's Algorithm,有 O(ElgV) 的堆实现和 O(V^2) 的普通数组实现两种。