【初阶数据结构与算法 2】时间/空间复杂度练习——转轮数组_数组转置时间复杂度

---

前言

前面学习了时间复杂度和空间复杂度相关的知识点，本文将通过练习题转轮数组，来巩固所学知识。

---

1、转轮数组

实现一个函数，可以轮转数组中的k个元素，例如：

1 2 3 4 5 6 7 
轮转3个元素，
即将 5 6 7 放到数组前面，得到
5 6 7 1 2 3 4
1
2
3
4

2、 方法1——数组

• 时间复杂度：O(k*N)，
• 内循环N次，外循环k次，k 最坏是 N-1，最好情况是 1
• 空间复杂度：O(1)
• 算法额外临时创建了3个变量

void leftChange1(int a[], int sz, int cnt)
{
	int tmp = 0;
	cnt = cnt % sz;//表示旋转几个字符,当轮转个数大于数组长度时，取模
	for (int k = 0 ; k < cnt; k++)
	{
		tmp = a[sz-1];
		for (int i = sz - 2; i >= 0; i--)
		{
			a[i+1] = a[i];//前面一项赋值给后一项
		}
		a[0] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、 方法2——指针

方法2和方法1没有区别

//基础解法2  用指针
void leftChange2(int* a, int sz, int cnt)
{
	int tmp = 0;
	cnt = cnt % sz;//表示旋转几个字符
	for (int k = 0; k < cnt; k++)
	{
		tmp = *(a + sz -1);
		for (int i = sz - 2; i >=0 ; i--)
		{
			*(a + i + 1) = *(a + i);
		}
		*a  = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4、 方法3——动态内存空间

用指针、字符串库函数、动态内存空间

• 时间复杂度：O(N)，数组a拷贝到pc，执行N次，在拷贝回a也是N次
• 空间复杂度：O(N)，算法临时开辟了N个空间

void leftChange3(int* a, int sz, int cnt)
{
	cnt = cnt % sz;
	int* pc = (int*)malloc(sz*sizeof(int));
	if (pc == NULL)
	{
		perror("malloc:");
		return;
	}
	memcpy(pc, a + sz - cnt, cnt * sizeof(int));//
	memcpy(pc + cnt, a , (sz-cnt) * sizeof(int));//
	memcpy(a, pc, sz*sizeof(int));//
	free(pc);
	pc = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5、 方法4——3次逆转

3次逆转，很难想到

• 时间复杂度：O(N)，数组a前半后半分别逆转，执行N次，最后整体逆转也是N次
• 空间复杂度：O(1)，算法临时建立了1N个临时变量

void reverse(int* a, int left, int right)
{
	while (left < right)
	{
		char tmp = a[left];
		a[left] = a[right];
		a[right] = tmp;
		left++;
		right--;
	}
}
void leftChange4(int* num, int sz, int cnt)
{
	cnt = cnt % sz;
	reverse(num, sz - cnt, sz-1);//后半部分
	reverse(num , 0 , sz-cnt-1);//前半部分
	reverse(num, 0, sz - 1);
}

int main()
{
	int a[] = { 1,2,3,4,5,6,7 };
	int sz = sizeof(a)/sizeof(a[0]);//数组个数
	//leftChange1(a, sz, 3);
	//leftChange2(a, sz, 3);
	//leftChange3(a, sz, 3);
	leftChange4(a, sz, 3);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

总结

时间复杂度和空间复杂度要牢记定义，多练习才能熟练掌握。

要做到不写代码，只分析思路就能知道时间复杂度的阶数。

初阶数据结构和算法建立在C语言之上的，学习这部分内容，要随时复习之前所学的知识。

下一篇将继续练习。