考虑下述选择排序算法: 算法 ModSelectSort 输入:n 个不等的整数的数组 A[..n] 输出:按递增次序排序的 A 1.for i-1 to n-1 do 2.for ji+1 to n do 3.if A[j]<A[] then A[iALj] 问: (1) 最坏情况下该算法做多少次比较运算? (2) 最坏情况下该算法做多少次交换运算?这种情况在什么输人条件下发生?

(1) 在最坏情况下，每次内层循环都需要比较n-i次，因此总的比较次数为:
(n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2
因此最坏情况下该算法需要进行O(n^2)次比较运算。

(2) 在最坏情况下，每次内层循环都需要执行一次交换操作，因此总的交换次数为:
(n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2
这种情况发生在数组原本就是逆序排列的情况下，即每次比较都需要交换两个元素的位置。

相关问题

给定n 个不同数的数组 S 和正整数 i，i<n^(1/2),求 S 中最大的i个数,并且按照从大到小的次序输出.有下述算法: 算法 A:调用i次找最大算法 Findmax,每次从 S 中删除一个最大的数。算法 B:对 S 排序,并输出 S 中最大的i个数. (1) 分析 A,B 两个算法在最坏情况下的时间复杂度 (2)试设计一个最坏情况下时间复杂度的阶更低的算法,要求给出伪码

(1) A算法的最坏情况下时间复杂度为O(n*i)，B算法的最坏情况下时间复杂度为O(n*logn)。

(2) 可以使用堆排序来实现，最坏情况下时间复杂度为O(n*logi)。具体伪码如下：

1. 建立一个大小为i的小根堆，将S中前i个数插入堆中。
2. 遍历S中剩余的数，对于每个数，如果它比堆顶元素大，则将堆顶元素弹出，将该数插入堆中。
3. 遍历完S后，堆中的元素即为S中最大的i个数，按照从大到小的次序输出即可。

1.4 计算下述算法所执行的加法次数 算法1 输入:n-2t ，t为正整数 输出:k 1. k←0 2. while n≥1 do 3. for j←1 to n do 4. k←k+1 5. n←n/2 6. return k

这个算法的基本思路是将n除以2，每次除以2之后循环次数减半，直到n小于1为止。在内部循环中，k的值会增加n次，因此内部循环的次数为n。假设一开始n为N，那么除以2后n的值为N/2，再除以2后n的值为N/4，以此类推。因此，对于每个除以2操作，内部循环的次数减半，直到内部循环的次数为1。所以内部循环总次数为N + N/2 + N/4 + N/8 + ... + 1。

这是一个等比数列，其和为N(1-1/2^t)/(1-1/2)。因此，内部循环总次数为2N-1，因为最后一次循环只有1次。因此，此算法执行的加法次数为2n-1，即O(n)。

因此，对于输入n-2t，此算法执行的加法次数为2(n-2t)-1，即O(n-t)。