tch*_*tch 6 algorithm math communication
这是一个“软性问题”，因此，如果此发布地点不合适，请告诉我。
本质上，我想知道如何谈论在某种意义上“等效”而在其他意义上“不同”的算法。
这是一个玩具示例。假设我们得到一个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可能是最著名的例子。
算法的维基百科页面提到“高级描述”，“实现描述”和“形式描述”。
显然，实现和形式描述有所不同，但是高级描述（例如“添加列表”）对两者是相同的。
这些是不同的算法，同一算法的不同实现还是完全不同？在谈论高级描述时，您将如何描述算法相同但实现不同的算法？
小智 1
可以在标签的信息algorithm中找到以下定义。
算法是基于形式语言的一组有序指令，具有以下条件：
有限。指令的数量必须是有限的。
可执行。所有指令都必须能够在有限的时间内以某种依赖于语言的方式执行。
特别考虑到
基于正式语言的一组有序指令
这告诉我们指令的顺序很重要。虽然两种不同算法的结果可能相同，但这并不意味着算法是相同的。
你的 Gram-Schmidt 与 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现在做与和相同的事情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 21.指令和上的情况正好相反3.，因此它们不一样。
但在这些不同的层面上，这些程序是等价的吗？根据韦氏词典，我想说它们是各个级别的。对于相同的输入，它们的“价值”或者更好的是它们的“输出”是相同的**。通信的问题在于，这些算法，就像您在问题中已经指出的那样，返回相同的结果，使它们等效但不相同。
您所指的**浮点不准确度意味着实现级别，这两种算法已经不同。作为数学模型，我们不必担心浮点不准确，因为数学中不存在这样的事情（数学家生活在一个“完美”的世界中）。
这些算法是同一高级描述的不同实现级别描述。因此，我会参考同一高级算法的 不同实现，因为想法是相同的。
最后一个重要的区别是通过将算法分配给其复杂性的集合来进一步形式化算法（正如 @jdehesa 的评论中完美指出的那样）。如果你只使用大的 omicron，那么......你的集合将会很大并且使更多的算法“等效”。这是因为归并排序和冒泡排序都是O(n^2)时间复杂度集合的成员（非常不精确，但n^2都是两者的上限）。显然冒泡排序不存在O(n*log[2](n))，但这个描述没有具体说明。如果我们使用大theta，那么冒泡排序和合并排序就不再属于同一组，上下文很重要。描述算法不仅仅是其步骤，这是您可以记住的区分算法的另一种方法。
总而言之：这取决于上下文，尤其是与您交谈的对象。如果您正在比较算法，请确保指定您正在执行的级别。对于业余爱好者来说，“添加列表”就足够了，因为您的文档使用高级描述，在解释您的代码时解释您对上述高级别的实现，以及当您确实需要在将其放入之前将您的想法形式化时代码使用正式的描述。后者还可以让您证明您的程序正确执行。当然，现在您不必再编写底层 TM 的所有状态。当您描述算法时，请以适合设置的形式进行。如果您有相同高级算法的两种不同实现，只需指出实现级别上的差异（遍历方向、求和实现、返回值格式等）。