#M9026. 复杂度分析
复杂度分析
当前没有测试数据。
- 基于比较的排序时间复杂度的下限是( ),其中n表示待排序的元素个数? {{ select(1) }}
- 完善程序:
(序列重排)全局数组变量 a 定义如下:
const int SIZE = 100;
int a[SIZE], n;
它记录着一个长度为n的序列 a[1],a[2],⋯,a[n]。 现在需要一个函数,以整数p(1≤p≤n)为参数,实现如下功能:将序列a 的前p个数与后n–p 个数对调,且不改变这p 个数(或n–p个数)之间的相对位置。例如,长度为 5 的序列 1, 2, 3, 4, 5,当p=2 时重排结果为3, 4, 5, 1, 2 。 有一种朴素的算法可以实现这一需求,其时间复杂度为、空间复杂度为 :
void swap1( int p )
{
int i, j, b[SIZE];
for ( i = 1; i <= p; i++ )
b[①] = a[i];
for ( i = p + 1; i <= n; i++ )
b[i - p] = ②;
for ( i = 1; i <= ③; i++ )
a[i] = b[i];
}
我们也可以用时间换空间,使用时间复杂度为、空间复杂度为的算法:
void swap2(int p)
{
int i, j, temp;
for ( i = p + 1; i <= n; i++ )
{
temp = a[i];
for ( j = i; j >= ④; j-- )
a[j] = a[j - 1];
⑤ = temp;
}
}
第一空:{{ input(2) }}
第二空:{{ input(3) }}
第三空:{{ input(4) }}
第四空:{{ input(5) }}
第五空:{{ input(6) }}
- 某算法的计算时间表示为递推关系式 (n 为正整数)及,则该算法的时间复杂度为? {{ select(7) }}
- 给定一个含N 个不相同数字的数组,在最坏情况下,找出其中最大或最小的数,至少需要 N−1 次比较操作。则最坏情况下,在该数组中同时找最大与 最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整,⌊ ⌋表示向下取整) {{ select(8) }}
- ⌈3N / 2⌉ - 2
- ⌊3N / 2⌋ - 2
- 2N - 2
- 2N - 4
- 冒泡排序算法的伪代码如下:
输入:数组L, n ≥ k。输出:按非递减顺序排序的 L。
算法 BubbleSort:
1. FLAG ← n //标记被交换的最后元素位置
2. while FLAG > 1 do
3. k ← FLAG -1
4. FLAG ← 1
5. for j=1 to k do
6. if L(j) > L(j+1) then do
7. L(j) ? L(j+1)
8. FLAG ← j
对 n 个数用以上冒泡排序算法进行排序,最少需要比较多少次?
{{ select(9) }}
- 以比较作为基本运算,在N个数中找出最大数,最坏情况下所需要的最少的比较次数为? {{ select(10) }}