1 
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 调用。:)

PS 我看到复杂度是 O(n)，但我需要尽可能准确地估计交换执行了多少次。

编辑 1：Swap(a,i,j)交换元素a[i]和a[j].

4

2 回答 2

1

设 s 和 r 是原始数组中最大和次大元素的位置。在第一个循环结束时：- 最大的将来到第一个位置。如果 r < s 那么下一个最大的位置现在将是 r。如果 r > s 它仍然是 r。在第二个循环结束时，下一个最大元素将在末尾。对于第一个循环，固定 s 的最坏情况是直到 s 的所有元素都按升序排列。交换次数为 s。对于第二个循环，如果下一个最大的更接近数组的开头，则会出现最坏的情况。当 r < s 并且最大元素之后的所有元素在原始数组中按降序排列时会发生这种情况（即使在第一个循环之后它们也将保持不变）。在最坏的情况下，交换次数为 ns-1 Total = n-1，与 r 和 s 无关。

例如 A = [1 2 5 7 3 4] 这里直到最大元素 7 它是上升的，然后下降的交换次数 = 5

于 2012-12-17T22:26:19.150 回答
0

第一个循环的最坏情况是每个a i都小于a j且 1 ≤ i < j ≤ n。在这种情况下，每个a j都与一个1交换，因此最后一个1是最大的数字。这种交换最多只能发生n -1 次，例如：

[1,2,3,4,5] ⟶ [5,1,2,3,4]

类似地，第二个循环的最坏情况是每个a i都大于a j且 2 ≤ i < j ≤ n。在这种情况下，每个a i都与a n交换，因此最后a n是子数组a 2 ,..., a n的最大数。这种交换最多只能发生n -2 次，例如：

[x,4,3,2,1] ⟶ [x,3,2,1,4]

现在棘手的部分是将两个条件结合起来，因为Swap两个循环中的调用条件是互斥的：对于任何对a i，a j且 1 ≤ i < j ≤ n和a i < a j，第一个循环将调用Swap. 但是对于任何这样的对，第二个循环都不会调用Swap，因为它期望相反：a i > a j。

所以最大Swap调用次数是n -1。

于 2012-12-17T22:11:18.483 回答