Algorithm(a-array, n-length):
for(i=2;i<=n;i++)
if(a[1]<a[i]) Swap(a,1,i);
for(i=n-1;i>=2;i--)
if(a[n]<a[i]) Swap(a,n,i);
我有兴趣确定多少次 Swap在最坏的情况下在上面的代码中被调用，所以我有一些疑问。
那里最坏的情况是什么？
- 如果我只有第一个 for 循环，可以说这个算法的最坏情况是数组 a 已经按升序排序，Swap 将被调用 n-1次。
- 如果我只有第二个循环，最坏的情况也是 a 已经排序，但这次，顺序是降序的。这意味着如果我们考虑第一个最坏的情况，
Swap不会在第二个循环中调用，反之亦然，即它不能在每次迭代的两个循环中调用。
我现在该怎么办？如何将这两个彼此相反的最坏情况结合起来？ 最坏的情况意味着我希望有尽可能多的 Swap 调用。 :)
附言我看到复杂度是 O(n)，但我需要尽可能准确地估计 Swap 执行了多少次。
编辑 1:Swap(a,i,j)交换元素 a[i]和 a[j] .
最佳答案
设 s 和 r 为原始数组中最大和次大元素的位置。在第一个循环结束时:- 最大的将排在第一位。 如果 r < s 那么下一个最大的位置现在将是 r。如果 r > s 它仍然是 r。 在第二个循环结束时，下一个最大的元素将在最后 对于第一个循环，固定 s 的最坏情况是 s 之前的所有元素都按升序排列。交换次数为 s。 对于第二个循环，如果下一个最大的更接近数组的开头，则会发生最坏的情况。当 r < s 并且最大元素之后的所有元素在原始数组中按降序排列时会发生这种情况(即使在第一个循环之后它们也不会被触及)。交换次数为n-s-1 在最坏的情况下总计 = n-1，与 r 和 s 无关。
例如 A = [1 2 5 7 3 4] 这里最多 7 个元素是上升的，然后是下降的 交换次数 = 5
关于algorithm - 函数被调用了多少次？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13922182/