函数调用了多少次？

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循环，可以说，对于这个算法最坏的情况是，该阵列一个已按升序排序，并交换会被称为N-1次。
如果我只有第二个循环，最坏的情况也会是a已经排序，但是这次订单会下降。这意味着如果我们考虑第一个最坏的情况，Swap将不会在第二个循环中调用，反之亦然，即在每次迭代中都不能在两个循环中调用它。

现在我该怎么办？如何将这两种相反的最差情况结合起来？最坏的情况意味着我想尽可能多地进行交换呼叫。：）

P.S.我发现复杂度是O（n），但我需要尽可能精确地估计Swap执行的次数。

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

来源

2012-12-17 Milos

是对第二个for循环内循环？ –

不，它不是。循环不嵌套。 – Milos

我已经对包含10个独特元素的数组的所有可能的排列组合测试了这种算法，并且在它们中的任何一个上执行的最多交换是9。从经验观察来看，n-1互换是大小为n的数组的最差情况。但我没有正式的证据，这就是为什么这是一个评论，而不是一个答案。 – Kevin

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

例如A = [1 2 5 7 3 4]以下高达最大elemnt 7它是升序和互换的该降数后= 5

来源

2012-12-17 22:26:19

谢谢你，Bug Catcher，你帮了我很多。：） – Milos

用于第一循环中的最坏情况是，每一个_我小于一个_Ĵ与1≤我 < Ĵ≤Ñ。在这种情况下，每一个_Ĵ被交换与一个，使得在端部一个是最大数目。这种交换只能发生在最ň -1倍，如：

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

同样，对于第二循环的最糟糕的情况是，每一个_我比一个_更大Ĵ用2≤我 < Ĵ≤ñ。在这种情况下，每一个_我被交换与一个_Ñ，使得在端部一个_Ñ是子阵列一个_{的数量最多2}，...，a_n。这种交换只能发生在最ň次-2次，如：

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

现在棘手的问题是相互排斥这两个条件的条件在这两个环的Swap呼叫相结合：对于任何一对一个_我，一个_Ĵ与1≤我 < Ĵ≤Ñ和一个_我<一个_Ĵ，第一环路会调用Swap。但任何这样的对，所述第二环路将不会调用Swap，因为它预期相反：一个_我>一个_Ĵ。

所以最大呼叫数Swap是n -1。

来源

2012-12-17 22:11:18 Gumbo

从我对Swap（A，i，j）的理解来看，这是一个在i和j位置交换元素的例程 –

@BugCatcher是的，你是对的。我想我忽略了这一点。 – Gumbo

是的，但遗憾的是忘记在代码中提到它：Swap（a，i，j）交换元素a [i]和a [j]，所以如果在第一次循环的第一次迭代中发现1 <3，则Swap交换1和3，所以我们有A = [3,1,3,3,2]。之后，当a [i] = 3,3,2时，Swap不会被调用，因为3 <3和3 <2都是错误的。第二个循环：现在A是[3,1,3,3,2]，当我们检查2和3（数组中的第4和第5个元素）时调用Swap，所以我们有[3,1， 3,2,3]在第二次迭代中。之后，因为3 <2,3 <3和3 <1是错误的，Swap在循环中不会再次被调用。 – Milos

函数调用了多少次？

回答

相关问题