这是一个“软性问题”,因此,如果此发布地点不合适,请告诉我。
本质上,我想知道如何谈论在某种意义上“等效”而在其他意义上“不同”的算法。
这是一个玩具示例。假设我们得到一个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
Run Code Online (Sandbox Code Playgroud)
对于数值算法,这是很常见的事情,例如,Gram-Schmidt与Modd Gram Schmidt可能是最著名的例子。
算法的维基百科页面提到“高级描述”,“实现描述”和“形式描述”。
显然,实现和形式描述有所不同,但是高级描述(例如“添加列表”)对两者是相同的。
这些是不同的算法,同一算法的不同实现还是完全不同?在谈论高级描述时,您将如何描述算法相同但实现不同的算法?