【数据结构开篇 --- 时间和空间复杂度】

发布时间:2023年12月22日

数据结构开篇

前言:
什么是程序?程序 = 算法 + 数据结构
可想而知对于一个完整的程序来说,数据结构的重要性;对于一个好的程序,数据结构能让我们更深层次的理解。
/知识点汇总/

1、介绍数据结构及算法

1.1、什么是数据结构?

数据结构是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

1.2、什么是算法?

算法就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。
简单说算法就是一系列的计算步骤,用来将输入数据转化为输出结果。

2、数据结构的重要性

数据结构是计算机科学中非常重要的一部分,它提供了存储和组织数据的方法和技术。 数据结构在计算机科学领域中经常用于解决许多不同类型的问题,包括信息搜索、排序、过滤等。
使用正确的数据结构可以使算法更加有效和高效,并且可以节省大量的计算资源。 数据结构也被广泛用于数据库、编译器、操作系统等领域中。
在数据库中,数据结构可以用来存储和管理大量的数据,并且可以支持数据的查询和更新等操作。
在编译器中,数据结构可以用来存储和管理程序的符号表和语法树等信息。
而在操作系统中,数据结构可以用来实现进程管理、文件系统和网络通信等功能。
掌握数据结构是计算机科学领域中的基础技能之一,它可以使程序员更好地理解和应用算法,并且可以使他们写出更高效、更可维护的代码。

3、如何衡量一个算法的好坏?

从数据结构角度理解分为:
(1).算法效率
(2).时间复杂度
(3).空间复杂度

3.1、算法效率

算法效率,如何衡量一个算法的好坏?
从算法的复杂度分析
一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度;
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。

3.2、时间复杂度

概念:从计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。
从理论上说,是计算不出来的,因为只有跑程序才能知道,所以一个算法所花的时间与其中语句执行的次数成正比例;
即算法中的基本操作的执行次数,为算法的时间复杂度。
简言之,对于一个程序来说,找到该程序的基本语句与问题规模之间的表达式,就能算出该算法的时间复杂度(估算值)。

举例1:

void fun1(int N)
{
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			++count;
		}
	}
	for (int k = 0; k < 2*N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

//演算:
//F(N) = NN + 2N + M(10)
//N = 10 — F(N) = 130 约等于 100
//N = 100 — F(N) = 10210 约等于 10000
//N = 1000 — F(N) = 1002010 约等于 1000000
//小结:
//观察N的取值,N越大项数间的影响越小;
//采用大O渐近表示法:估算 — 取影响最大的项,忽略常数项
//F(N) == O(n^2)

举例2:

void fun2(int N)
{
	int count = 0;
	for (int k = 0; k < 2*N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

//演算:
//F(N) = 2*N + M(10)
//当N无限大后,系数就影响不大了;与常数项一样忽略系数即可
//计算的是量级:
//F(N) == O(N)

举例3:

void fun3(int N,int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

//演算:
//O(M+N)?
//通常带值验算:
//当N远大于M --> O(N)
//当M远大于N --> O(N)
//当N与M相近 --> O(N)orO(M)
//小结:得–>O(max(M,N))

举例4:

void fun4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

//演算:
//常数项就是O(1)
//O(1)并不是代表一次执行次数,而是表示常熟项

补充:大O渐近表示法
大O符号:是用于描述函数渐近行为的数学符号。
推导大O阶方法
1.用常数1取代运行时间中所有的加法常数。
2.在修改后的运行次数函数中,只保留最高阶项(取决定性的那一项)。
3.如果最高阶项存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶(即去掉系数)。

时间复杂度中的最好、最坏、平均情况 — 思考
结论:最好就是最坏的情况,因为时间复杂度采取预期管理法,以最坏的结果作为保守估计。看思想,不能单纯的看循环的嵌套

**举例5:**冒泡排序

void bubblesort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; i++)
		{
			if (a[i - 1] > a[i])
			{
				swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchenge == 0)
			break;
	}
}

//演算:
//F(N) = N*(N-1)/2 — 等差数列
//O(N^2)

举例6:

int PartSort1(int* a, int left, int right)
{
	//int midi = GetMidi(a, left, right);
	//Swap(&a[left], &a[midi]);
	int keyi = left;
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[left]);
}

//演算:
//F(N) = left + right = N
//O(N)

举例7:

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

//演算:
//O(logN)

举例8:

long long fac(size_t N)
{
	if (0 == N)
		return 1;
	return fac(N - 1) * N;
}

//演算:
//F(N) = N + (N-1) + (N-2)… + 0
//O(N)

举例9:

long long fac(size_t N)
{
	if (0 == N)
		return 1;
	for (size_t i = 0; i < N; i++)
	{
		//....
	}
	return fac(N - 1) * N;
}

//演算:
//F(N) = N*(N-1)+(N-1)(N-2)+…*1
//O(N^2)

举例10:

long long fib(size_t N)
{
	if (N < 3)
		return 1;
	return fib(N - 1) + fib(N - 2);
}

//演算:
//F(N) = 2^0 + 2^1 + 2^2 +…+2(N-4)+2(N-3)+2^(N-2)
//等比数列和:F(N) = 2^(n-2) + 2^(n-3) + …+2^2 + 21+20
//错位相减法,左右两边各乘一个2
//F(N) = 2^(N-1) - 2^0
//O(2^N)
// 斐波那契数这种方法时间复杂度太高,所以建议采用三个变量的方式解决。

小结
时间复杂度,需要看思想,不能单纯的看循环
即时间复杂度计算不能数代码的循环,需要根据思想,灵活计算。

3.3、空间复杂度

概念:空间复杂度也是一种数学表达式,是对一个算法需求,在运行过程中临时额外占用存储空间大小的量度。
空间复杂度不仅是程序占用了多少个bytes的空间,因为这个也没太大的意义,所以空间复杂度算的是变量的个数。
也采用大O渐近表达法
值得注意的是:函数运行时所需要的栈空间(存储参数、局部变量,一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时显示申请的额外空间来确定

举例1:

void Bubblesort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a]i);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

//S(N) = 1
//O(1) — 变量的个数

举例2:

long long* fibonacci(size_t n)
{
	if (n == 0)
		return NULL;
	long long* fibarray = (long long*)malloc((n + 1) * sizeof(long long));
	fibarray[0] = 0;
	fibarray[1] = 1;
	for (int i = 0; i <= n; i++)
	{
		fibarray[i] = fibarray[i - 1] + fibarray[i - 2];
	}
	return fibarray;
}

//S(N)= 1+1+(2~N) = N
//O(N)

**举例3:**斐波那契数

long long fib(size_t N)
{
	if (N < 3)
		return 1;
	return fib(N - 1) + fib(N - 2);
}

//斐波那契数的空间是重复利用的,因为递归结束后会释放,相当于重复利用同一块空间。
//递归空间复杂度计算,也是空间累加,但是不同的是空间可以重复利用。
//空间可重复利用、时间不能重复利用
//空间复杂度:O(N)

4.时间复杂度和空间复杂度,巩固练习

4.1、练习题1:移除元素

方法1:空间换时间

#include <stdio.h>
#include <stdlib.h>
int removeElement(int* nums,int sz,int val)
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	int src = 0;
	int dst = 0;
	while (src < sz)
	{
		if (nums[src] == val)
		{
			src++;
		}
		else
		{
			tmp[dst] = nums[src];
			dst++;
			src++;
		}
	}
	for (int i = 0; i < sz; i++)
	{
		nums[i] = tmp[i];
	}
	free(tmp);
	tmp = NULL;
	return dst;
}
int main()
{
	int nums[8] = { 0,1,2,2,3,0,4,2 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	int val = 2;
	int ret = removeElement(nums, sz, val);
	for (int i = 0; i < ret; i++)
	{
		printf("%d ",nums[i]);
	}
	return 0;
}

方法2:移动覆盖

#include <stdio.h>
#include <stdlib.h>
int removeElement(int* nums, int numsSize, int val)
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if (nums[src] != val)
		{
			nums[dst] = nums[src];
			dst++;
			src++;
		}
		else
		{
			src++;
		}
	}
	return dst;
}
int main()
{
	int nums[8] = { 0,1,2,2,3,0,4,2 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	int val = 2;
	int ret = removeElement(nums, sz, val);
	for (int i = 0; i < ret; i++)
	{
		printf("%d ", nums[i]);
	}
	return 0;
}

4.2、练习题2:反转数组

思路1:时间复杂度 考虑最好、平均、最坏旋转次数 k%N —>实际的时间复杂度O(NN)
最好情况:O(1) k%N == 0,k为N的倍数时,不需要旋转;
最坏情况:K%N == N-1时
N
(N-1) -> O(N^N)
每右旋一次为N ,最多右旋N-1次–>O(N^N)

如何优化到O(N)?
思路2:三步翻转法:前k个逆置,后k个逆置,整体逆置
关键点是:k %= numsSize; O(N)

#include <stdio.h>
void reverse(int* a, int left, int right)
{
	while (left < right)
	{
		int tmp = a[left];
		a[left] = a[right];
		a[right] = tmp;
		++left;
		--right;
	}
}
void rotate(int* nums, int numsSize, int k)
{
	k %=  numsSize;
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, numsSize - k, numsSize-1);
	reverse(nums, 0, numsSize- 1);
}
int main()
{
	int a[7] = { 7,1,2,3,4,5,6 };
	rotate(a, 7, 1);
	for (int i = 0; i < 7; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

思路3:空间换取时间的处理方法
时间复杂度O(N),空间复杂度O(N)
开辟一个新数组,然后分别拷贝前k的数据,拷贝到新数组的后面;
后k个数据拷贝到新数组的前面即可,最后遍历还给nums。

#include <stdio.h>
#include <stdlib.h>
void rotate(int* nums, int numsSize, int k)
{
	k %= numsSize;
	//int tmp[numsSize];//变长数组,变长数组不能初始化,想要初始化需要用memset实现
	int* tmp = (int*)malloc(sizeof(int) * numsSize + 16);
	int j = k;   //关键在于注意下标的控制
	//拷贝前k个数据
	for (int i = 0; i < numsSize - k; i++)
	{
		tmp[j++] = nums[i];
	}
	//拷贝后k个数据
	j = 0;
	for (int i = numsSize - k; i < numsSize; i++)
	{
		tmp[j++] = nums[i];
	}
	//还给nums数组
	for (int i = 0; i < numsSize; i++)
	{
		nums[i] = tmp[i];
	}
	free(tmp);
	tmp = NULL;
}
int main()
{
	int a[7] = { 7,1,2,3,4,5,6 };
	rotate(a, 7, 1);
	for (int i = 0; i < 7; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}
文章来源:https://blog.csdn.net/m0_69455439/article/details/135150952
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。