这个问题来自这个答案的评论中的讨论.
首先,让我们说定义乱序是很困难的.以Pavel Shved为例,在列表[1,5,10,2,3,4,5,6,7,8,9,10,11]中我们可以"清楚地"看到5和10(指数1) 2)发生故障.但是一个简单地检查某种排序列表不变量的简单算法并不能指出这些算法.
检查a[i-1]<=a[i] for all 0<i<=N会产生索引3处的元素(即2);
检查a[j]<=a[i] for all 0<=i<=N and 0<=j<=i会产生索引3到12中的所有元素;
我的问题是:你能想到一个算法来解决这个产生"正确答案"(即指数1和2)的问题吗？如果是这样,它会在什么时间和内存复杂度下运行？