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

数据结构开篇

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

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 + 2¹⁺²0
//错位相减法，左右两边各乘一个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;
}