算法步骤的正式定义是什么？

Question

考虑下面的代码来查找数组的K最小元素：

FindKthMin(A[], k)
{
    A = Sort(A);
    return A[k];
}

它是否是一种不指定sort细节的算法？

如果不指定指令集(目标机器及其基本指令集)，我们可以说算法没有任何意义吗？

例如，在BubbleSort中，我们应该指定Swap(..)或Add(..)详细信息吗？我的意思是，那些原子指令会阻止我们更进一步吗？

或者，算法步骤的正式定义是什么？它有什么一般的数学定义(像函数之类的)吗？

Answer 1

如果不首先定义什么是“步骤”，那么谈论算法的步骤复杂性是没有意义的。算法的复杂性总是与计算模型有关，无论是图灵机的转换、λ演算的缩减、随机存取机器的指令，还是在讨论基于比较的排序(如冒泡排序、快速排序、合并排序、tim排序等)时的比较次数。

还要注意的是，算法根本不需要有“步骤”。模拟算法是连续的，它们没有步骤。