0.引言
在我们的日常生活中，经常需要管理大量的数据，就譬如学校中有好几千个学生，中国有十三亿人口，对于那么多的数据进行查找、插入、排序等操作就会比较慢。人们为了解决这些问题，提高对数据的管理效率，提出了一门学科：数据结构与算法
1.什么是数据结构
数据结构是由“数据”和“结构”两词组合而来。
什么是数据？
常见的数值1、2、3、4......、学生管理系统中保存的学生信息（学号、年龄、年级等到）都是数据
什么是结构？
我们想要大量的使用某一个类型的数据时，需要手动定义大量的独立的变量对于程序来说，可读性非常差，因此我们会借助数组这样的数据结构将大量的数据组织在一起，结构就可以理解为组织数据的方式。
打个比喻，如果我们把叫“裤衩”的羊放生到草原上，我们自然很难找到它；但，如果我们把这只羊放到羊圈里，我们就可以很轻松的找到它。
2.什么是算法
对于我们在这个地方的学习而言，算法就是一个计算过程，它指的是一系列的计算步骤，用来将输入的数据转化成为输出的结果。
而在我们的课程内，我们需要学习的算法是：搜索、排序，递归、分治、回溯、DP、贪心。
算法是一个很让人头疼的东西，学习算法就像学习数学，而且初学时往往一道题做着做着几个小时就过去了...... 但，持之以恒，每个类型的题目都积累了一定数量了之后，算法对于我们而言便小菜一碟了。
在我们数据结构这本书上，我们会学到的算法是搜索和排序以及一部分的递归算法。
3.复杂度分析
3.1算法评估
我们的学习数学的过程中，经常会遇到一题多解的情况出现，而其中总有一种方法会被称为最优解。
我们对一个编程问题的解决也是如此，可能两段程序拥有相同的入口，也可以达到相同的目标。
那么，我们如何判断两段程序的优劣呢？
我们在判断程序的优劣，自然而然的就可以想到两个方面的问题：
- 时间效率：算法运行的快慢
- 空间效率：算法所占空间的大小
3.2评估方法
评估时间的方法：
- 实验分析法
- 理论分析法
3.2.1实验分析法
实验分析法简单来说就是将不同的算法输入到同一台电脑上，统计时间的快慢。但是这种方法有两个缺陷：
- 无法排查实验自身条件与环境的条件的影响：比如同一种算法在不同配置的电脑上的运算速度可能不同，甚至结果完全相反。我们很难排查所有的情况
- 成本太高：同一种算法可能在数据少时表现不明显，在数据多时速率教快（学到排序后大家就可以理解这一句话了）。而且哪来那么多电脑给你做实验......
3.2.2理论分析法
由于实验分析法的局限性，就有人提出了一种理论测评的方法，就是渐进复杂度分析，简称复杂度分析。
这种方法体现算法运行所需的时空资源与输入数据大小之间的关系，能够有效的反应处算法的优劣。
4.时间复杂度和空间复杂度
4.1空间复杂度
一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
我们现在假设每条语句执行所用的时间为1ns
那么，以下这段代码执行所需时间：
int main()
{
int a = 3;//1
int b = 5;//1
int c = a + b;//1
int n = 0;//1
scanf("%d ", &n);//1
for (int i = 0; i < n; i++)
{
printf("%d ", i);//n
}
printf("%d ", c);//1
return 0;
}计算时间如下：
如果，n趋于正无穷时，那么，式子内的常数6的影响是微乎其微的，我们就可以将其忽略掉。
现在，我们改写一下这段代码
int main()
{
int a = 3;//1
int b = 5;//1
int c = a + b;//1
int n = 0;//1
scanf("%d ", &n);//1
for (int i = 0; i < 3n; i++)
{
printf("%d ", i);//3n
}
printf("%d ", c);//1
return 0;
}此时，它的时间为：
在刚刚，我们已经发现常数可以忽略了，现在我们同样让n趋于正无穷，这时我们发现，3n和n的极限都是正无穷，那么，它的系数影响的也不大了。因此，我们也可以把系数忽略掉。
现在，我们再改写一下代码：
int main()
{
int a = 3;//1
int b = 5;//1
int c = a + b;//1
int n = 0;//1
scanf("%d ", &n);//1
for (int i = 0; i < 3n; i++)
{
printf("%d ", i);//n
}
for (int i = 0; i < n^2; i++)
{
printf("%d ", i);//n的平方
}
printf("%d ", c);//1
return 0;
}此时，它的时间为：
显而易见的是，随着n的扩大，n^2的变化率必然是要比n高的。
譬如，当n等于一千时，n^2就是一百万了。
假如说一个国家有一百万零一千个兵，那么，战死了一千个兵会影响到别的国家对这个国家的评估吗？
这是显然不会的。
同理，在我们对算法的评估中，我们也不会在乎这个影响，因此，我们也可以将n忽略掉。
根据刚刚所说的内容，我们继续向外推导，如果一个数是指数，那么自然也就可以忽略这个平方了。
现在给大家介绍一个概念：“阶”
在数学和计算机科学中，"阶"通常指的是函数的增长速度，特别是在描述算法的时间复杂度时。阶通常与函数的输入规模n相关，用来表示随着输入规模n的增加，函数值增长的速度。
通过上述的推导过程，我们可以得到这么一个结论：
- 最高阶项的增长速度远超过其他低阶项，因此低阶项的影响可以忽略不计。
也就是说，阶数高的可以忽略阶数低的。
现在，我们发现，时间复杂度的计算可以简化为两个步骤：
- 忽略除最高阶以外的所有项
- 忽略所有系数
这里需要我们大家注意的一点是：我们对时间复杂度的理论推导是基于理论的，而不是基于实例。
然后现在我们学习一下如何记录时间复杂度：
譬如上面的一段代码，时间复杂度为O（n^2），这种方法称为大O的渐进表示法。
现在给大家写一个O（1）的代码
int main()
{
int a = 3;//1
int b = 5;//1
int c = a + b;//1
return 0;
}时间：
我们认为3是1的系数，因此这段代码的时间复杂度为O（1），表示常数阶。
最后一个需要大家注意的点是：
- 在计算复杂度时，我们考虑最坏的情况，不是最坏的情况算出的时间复杂度都是错误的。
4.2空间复杂度
空间复杂度也是一个数学表达式，它的计算方式和空间复杂度是一样的。
在这里，它计算的是一个算法在运行过程中临时占用存储空间大小的量度。
这里，我们关心的是临时变量占用存储空间的量度，而不是具体的变量大小。
也就是说，我们关心的是创建的临时变量的个数，而不关心具体的大小。
下面给大家算几个实例：
//这段代码在有的编译器过不了，大家可能无法运行
void func()
{
int n = 0;
scanf("%d ", &n);
int arr[n];//开辟了n个空间
}这段代码中，开辟了n个空间，空间复杂度为O(n)。
void Swap(int a,int b)
{
int c = a;
a = b;
b = c;
}开辟了一个整型的空间，空间复杂度为O（1）
由于1KB=1024Byte ,所以1MB＝1024*1024＝1048576字节，大概就是一百万字节。
一百万字节能存的变量可太多了，因此我们现在更加关注时间复杂度而不是空间复杂度。
5.常见时间复杂度
冒泡排序：
void bubble_sort(int* arr, int sz)
{
for (int i = 0; i < sz-1; i++)
{
int flag = 1;
for (int j = 0; j < sz-1- i; j++)//每次都可以少比较一个数
{
if (arr[j] > arr[j + 1])
{
flag = 0;
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (flag == 1)
break;
}
}
int main()
{
int arr[] = { 8,3,2,7,10,9,1,0,7,4};
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
for (int i= 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}时间复杂度O(n^2);空间复杂度O（1）
折半查找：
int binarySearch(int arr[], int size, int key) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == key) {
return mid; // 找到键值，返回下标
} else if (arr[mid] < key) {
left = mid + 1; // 键值在右侧子数组
} else {
right = mid - 1; // 键值在左侧子数组
}
}
return -1; // 未找到键值，返回-1
}时间复杂度：O（logn) 空间复杂度：O（1）
