algorithm - 如何引用 "equivalent"算法

Question

这是一个“软性问题”，因此，如果此发布地点不合适，请告诉我。

本质上，我想知道如何谈论在某种意义上“等效”而在另一些意义上“不同”的算法。

这是一个玩具示例。假设我们得到了一个长度为list的数字n的列表。下面给出了两种将列表中的数字相加的简单方法。显然，这些方法在精确算术中完全相同，但是在浮点算术中可能给出不同的结果。

add_list_1(list,n):
    sum = 0
    for i=1,2,...,n:
        sum += list[i]
    return sum

add_list_2(list,n):
    sum = 0
    for i=n,...,2,1:
        sum += list[i]
    return sum

对于数值算法而言，这是非常普遍的事情，例如，Gram-Schmidt与Modd Gram Schmidt可能是最著名的例子。

算法的维基百科页面提到“高级描述”，“实现描述”和“形式描述”。

显然，实现和形式描述有所不同，但是高级描述(例如“添加列表”)对两者是相同的。

这些是不同的算法，同一算法的不同实现还是完全不同？在谈论高级描述时，您将如何描述算法相同但实现不同的算法？

Answer 1

可以在Info for the algorithm tag上找到以下定义。

An algorithm is a set of ordered instructions based on a formal language with the following conditions:

Finite. The number of instructions must be finite.

Executable. All instructions must be executable in some language-dependent way, in a finite amount of time.

特别考虑

set of ordered instructions based on a formal language

这说明指令的顺序很重要。尽管两种不同的 算法的 结果可能是相同的，但这并不意味着算法是相同的。

您对Gram-Schmidt与修改的Gram-Schmidt进行的比较很有趣。从定义为 here的每种算法的结构来看，即使在高级描述上，它们的确是不同的算法。步骤以不同的顺序进行。

您需要做的一个重要区别是在一组指令和输出集之间。 Here您可以找到三种最短路径算法的描述。基于输入的可能结果集是相同的，但是它们是三种截然不同的算法。他们还具有三个完全不同的高级描述。对于不关心这些的人，尽管这些“做相同的事情”(写这篇文章几乎让我很伤心)，并且是 equivalent。

另一个重要的区别是算法之间的步骤相似。让我们以您的示例为例，并用更正式的形式编写它:

procedure 1 (list, n):
    let sum = 0
    for i = 1 : n
        sum = sum + list[i]
    end for
    sum //using implicit return

procedure 2 (list, n):
    let sum = 0
    for i = n : 1
        sum = sum + list[i]
    end for
    sum //using implicit return

这两段代码具有相同的结果集，但指令的顺序似乎不同。从高水平来看，这仍然是不正确的。这取决于您如何规范程序。循环是如果将它们简化为索引会改变过程的事情之一。不过，在这种特殊情况下(如注释中已经指出的那样)，我们可以从本质上将循环替换为更形式化的 for each循环。

procedure 3 (list):
    let sum = 0
    for each element in list
        sum = sum + element
    end for
    sum

现在 procedure 3与 procedure 1和 procedure 2具有相同的功能，它们的结果相同，但说明又一次不同。因此，这些过程是等效的算法，但在实现级别上是不同的。它们不一样，因为 procedure 1和 procedure 2的求和指令执行顺序不同，并且在 procedure 3中被完全忽略(取决于 for each的实现!)。

这就是高级描述的概念出现的地方。正如您已经指出的，这三种算法都是相同的。以下是您所指的 Wikipedia article。

1 High-level description

"...prose to describe an algorithm, ignoring the implementation details. At this level, we do not need to mention how the machine manages its tape or head."

2 Implementation description

"...prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level, we do not give details of states or transition function."

3 Formal description

Most detailed, "lowest level", gives the Turing machine's "state table".

请牢记这一点，您的问题实际上取决于所提出的上下文。所有三个高级过程都是相同的:

1. Let sum = 0
2. For every element in list add the element to sum
3. Return sum

我们不在乎我们如何浏览列表或如何求和，仅是我们这样做。

在实现级别上，我们已经看到了分歧。这些过程在“磁带”上的移动方式不同，但以相同的方式存储信息。当 procedure 1从开始位置在磁带上“向右”移动时， procedure 2从“结束”在磁带上“向左”移动(请注意这一点，因为TM中没有这样的东西，必须用不同的状态来定义它) ，我们不在此级别中使用)。 procedure 3，它的定义不够好，无法进行区分。

从低层次上讲，我们需要非常精确。我不会深入到TM状态表的级别，因此请接受这个相当非正式的过程描述。
procedure 1:

1. Move right until you hit an unmarked integer or the "end" 
//In an actual TM this would not work, just for simplification I am using ints
    1.e. If you hit the end terminate //(i = n)
2. Record value //(sum += list[i]) (of course this is a lot longer in an actual TM)
3. Go back until you find the first marked number
4. Go to 1.

procedure 2与 1.和 3.指令相反，因此它们是不同的。

但是，在这些不同的级别上，这些程序是否等效？根据 Merriam Webster，我会说它们在各个层面上。对于相同的输入**，它们的“值”或更好的“输出”是相同的。交流的问题在于，这些算法(如您在问题中已经提到的)返回相同的值，从而使它们等效但不相同。

您指的是**浮点不准确度，意味着实现级别，在这两种算法上，它们已经有所不同。作为数学模型，我们不必担心浮点误差，因为数学中没有这样的东西(数学家生活在“完美”的世界中)。

这些算法是同一高级描述的不同实现级别描述。因此，由于思想相同，因此我将引用同一高级算法的不同实现。

最后一个重要的区别是，通过将算法分配给集合以提高算法的复杂度来进一步形式化算法(如@jdehesa的注释中完美指出的那样)。如果您只使用较大的微米，那么...您的集合将会很大，并使更多的算法“等效”。这是因为合并排序和冒泡排序都因为其时间复杂性而同时是集合 O(n^2)的成员(非常不精确，但是 n^2是这两者的上限)。显然，冒泡排序不在 O(n*log[2](n))中，但此描述未指定。如果我们使用大theta，则冒泡和合并排序不再位于同一集合中，上下文很重要。描述算法不只是其步骤，还有很多别忘了区分算法的方法。

总结一下:这取决于 上下文，尤其是您正在和谁聊天。如果要比较算法，请确保指定要执行的级别。一位业余爱好者说“添加列表”就足够了，因为您的文档使用了高级描述，在解释代码时解释了以上高级的实现，以及您真正需要在将其放入之前将其思想形式化的情况代码使用正式描述。后期还将允许您 prove that your program executes correctly。当然，如今，您不必再编写基础TM的所有状态。描述算法时，请以适合设置的形式进行。并且，如果您对同一高级算法有两种不同的实现，则只需指出实现级别上的差异(遍历的方向，求和的实现，返回值的格式等)。