algorithm - 如何引用“等效”算法

可以在标签的 Info 中algorithm找到以下定义。

算法是一组基于形式语言的有序指令，具有以下条件：

有限。指令的数量必须是有限的。

可执行。所有指令都必须在有限的时间内以某种与语言相关的方式执行。

特别考虑

基于形式语言的有序指令集

这告诉我们指令的顺序很重要。虽然两种不同算法的结果可能相同，但这并不意味着算法相同。

你的 Gram-Schmidt vs. Modified Gram-Schmidt 的例子很有趣。看看这里定义的每个算法的结构，这些确实是不同的算法，即使在高级别的描述上也是如此。这些步骤的顺序不同。

您需要区分的一个重要区别是一组指令和输出集。在这里您可以找到三种最短路径算法的描述。基于输入的可能结果集是相同的，但它们是三种非常不同的算法。他们也有三个完全不同的高级描述。对于那些不关心这一点的人，尽管这些“做同样的事情”（写这个几乎伤害了我）并且是等价的。

另一个重要区别是算法之间步骤的相似性。让我们举个例子，用更正式的符号来写它：

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 3procedure 1现在与and做同样的事情procedure 2，它们的结果是一样的，但指令似乎又不同了。所以这些过程是等效的算法，但在实现层面上并不相同。它们是不一样的，因为求和指令的执行顺序是不同的procedure 1，procedure 2并且完全被忽略procedure 3（这取决于你的实现for each！）。

这就是高级描述概念的用武之地。正如您已经指出的，所有三种算法都是相同的。以下内容来自您所指的维基百科文章。

1 高层描述

“......散文描述算法，忽略实现细节。在这个级别，我们不需要提及机器如何管理它的磁带或磁头。”

2 实现说明

“...散文用于定义图灵机使用其磁头的方式以及它在磁带上存储数据的方式。在这个级别上，我们不提供状态或转换函数的详细信息。”

3 形式描述

最详细的“最低级别”给出了图灵机的“状态表”。

牢记这一点，您的问题实际上取决于它所处的上下文。所有三个高级程序都是相同的：

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的说法，我会说他们处于各个层面。对于相同的输入**，它们的“价值”或更好的“输出”是相同的。沟通的问题在于，这些算法，就像您在问题中已经说过的那样，返回相同，使它们等效但不相同。

您指的是 **floating point inaccuracy 意味着实现级别，这两种算法已经不同。作为一个数学模型，我们不必担心浮点数的不准确性，因为数学中不存在这样的事情（数学家生活在一个“完美”的世界中）。

这些算法是同一高层描述的不同实现层描述。因此，我会参考相同高级算法的 不同实现，因为想法是相同的。

最后一个重要的区别是通过将算法分配给一个复杂的集合来进一步形式化算法（正如@jdehesa 的评论中完美指出的那样）。如果你只使用大 omicron，那么......你的集合将是巨大的，并使更多的算法“等效”。这是因为归并排序和冒泡排序都是O(n^2)时间复杂性的集合的成员（非常不精确，但n^2都是两者的上限）。显然冒泡排序不在其中，O(n*log[2](n))但此描述并未具体说明。如果我们使用大 theta，那么冒泡排序和归并排序不再在同一个集合中，上下文很重要。描述算法不仅仅是它的步骤，这是您可以记住区分算法的另一种方法。

总而言之：这取决于上下文，尤其是与您交谈的人。如果您正在比较算法，请确保指定您正在执行的级别。对于业余爱好者来说，“加起来”就足够了，因为您的文档使用高级描述，在解释您的代码时解释您对上述高级别的实现，以及当您确实需要在放入之前将您的想法正式化时代码使用正式的描述。后者还将允许您证明您的程序正确执行. 当然，现在您不必再编写底层 TM 的所有状态。当您描述您的算法时，请以适合设置的形式进行。如果您有相同高级算法的两种不同实现，只需指出实现级别的差异（遍历方向、求和的实现、返回值的格式等）。

algorithm - 如何引用“等效”算法

问题描述

解决方案

推荐阅读