我更喜欢尽可能少的正式定义和简单的数学.
algorithm complexity-theory big-o computer-science time-complexity
例如,输入是
Array 1 = [2, 3, 4, 5]
Array 2 = [3, 2, 5, 4]
需要的最小交换次数是2.
交换不需要与相邻的单元相交,任何两个元素都可以交换.
设A是一个大小的数组N.(i,j)如果i < j和,我们将几个索引称为"反向"A[i] > A[j]
我需要找到一个接收大小数组N(带有唯一数字)的算法,并返回时间的倒数O(n*log(n)).
哪种排序算法产生的中间排序是好的近似值？
通过"良好的近似",我的意思是根据Kendall的tau和Spearman的脚趾等指标来确定有序列表与另一个列表的"远"(在这种情况下,确切的排序)
我想到的特定应用是人类进行主观成对比较的地方,并且可能无法进行所有n log n比较,例如heapsort或best-case quicksort.
哪些算法比其他算法更快将列表提升到接近/近似排序？