初识算法与数据结构
初始数据结构
数据结构是学习存储方式的一门学科。
怎样才算是一个好的算法。
数据结构有几种存储结构：
- 线性表，还可以细分为顺序表，链表、栈和队列；
- 树结构： 普通树、二叉树、线索二叉树等
- 图存储结构。
线性表
线性表结构一般采用依次排列的，属于一对一的关系，而具备这种一对一的关系的数据就可以使用线性表来存储。
线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。
顺序表
对于新手来说，可以将顺序表先简单的当作一个数组来理解。但是实际上数据结构是研究数据存储方式的一门学科，他囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。
链表
我们知道使用顺序表的时候，需要提前申请一定大小的存储空间，这段存储空间的物理地址是连续的。如上图所示。
而链表则完全不同，使用链表存储数据时，是随用随申请，因此数据存储的位置是相互分离的，也就是说每个数据存放的位置都是随机的，根据当时所申请的内存位置来决定数据存放的位置。
而为了给数据块建立依次排列的关系.，链表给各数据块增设了一个指针，每个数据块的指针都会指向下一个数据块(最后一个数据块的指针指向NULL)，就如同一个个小学生都伸手拉住下一个小学生的手，这样，我们就将看似毫无关联的数据块串联起来建立了依次排列的关系。形成了链表的存储方式。
栈和队列
栈中的元素只能从线性表的一端进入(另一端封死)，且要遵循“先入后出”的原则，即先进栈的元素后出栈。
队列中的元素只能从线性表的一端进入，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。
树结构
就是表示一种一对多的关系。
图结构
表示多对多的一种结构。
怎样才能称得上好的算法
解决一个问题的方法可能有很多，但称的算法的，首先必须要使这个算法能够彻底的解决这个问题，这就是我们所说的准确性，而且根据其编写的程序在任何情况下都不会出现崩溃的情况。这是我们所说的健壮性。
当然除了这两个方面还有一个重要的筛选条件，即通过算法所编写的程序的运行效率，具体的可以从两方面来衡量：
- 程序的运行时间
- 程序运行所需内存空间的大小
根据算法编写的程序，运行时间更短，运行时间占用的内存更少，该算法的运行效率就更高，算法也就个更好。
而在数据结构中，用时间复杂度来衡量程序运行时间的多少；用空间复杂度来衡量运行所需的内存空间的大小。
时间复杂度
判断一个算法的时间复杂度因为它会因为多种因素的影响，并不是我们将程序编写出来，然后在计算机中运行然后测量消耗的时间，不这样做的原因很简单，解决一个问题的算法有很多种，一一将其实现是基本不可能的是事情，而且，在不同的计算机中，因为计算机的软硬件的不一样从而导致程序在不同的计算机中的运行效率也是不一样的，即使是不同时间段的系统执行同一段程序也是会执行出不一样的运行时间，这样测量严重时甚至会导致误判。
这个时候我们就需要用一个估值来表示算法所编写的程序的运行时间，虽然估值无法准确的表示算法的表示算法所编程序的运行时间，但它的结果并非凭空揣测，也是计算后的结果。
也就是说一个算法的运行时间是多少，用的不是一个准确值，而是一个根据合理方法得到的预估值。例如：
for(int i = 0 ; i < n ; i++){ //<-从0到n，执行n+1次
a++; //<-从0到n-1，执行n次
}
所以这段代码所有语句共执行了(n+1)+n次，数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。
for(int i = 0 ; i < n ; i++){ //n+1
for(int j = 0 ; j < m ; j++){ //n(m+1)
num++; //n*m
}
}
这段代码的频度就是(n+1)+n(m+1)+n*m，简化一下就是2nm+2n+1。就上述程序而言，不同程序的运行时间，更多的场景中比较的是在最坏的条件中的运行时间，而上述程序最会的条件无非就是n和m都接近无限大时，我们完全可以认为m==n，那么，这段程序还可以进行简化，然后将它和第一段程序的曲线图进行比较：
这样一比较就很明显了，第一段程序运行的时间更短，运行更快。
我们思考一个问题，这样的式子还能再简化么，答案是肯定的，
就以2n+1为例，当n无限大时，是否在2n的基础上在做+1操作，并无关紧要，因为当n无限大时加不加一和乘不乘以2都是无关紧要的。
再用这种思想来思考第二个式子，我们可以直接简化为n的平方。
有些人还是不明白其中是怎样简化的，我给大家解释一下：
- 去掉频度表达式中，所有的加法常数式子
- 如果表达式与多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。
- 如果最高项存在系数，直接去掉系数。
事实上，对于一个算法来说(或者一段程序)来说，其最简频度往往就是最深层次的循环
结构中某一条语句的执行次数。例如2n+1最简为n，实际上就是a++语句的执行次数；另
一个式子简化也是一样，实际上就是最内层循环中num++语句的执行次数。
根据上面的算法计算，我们可以得到一段简短的式子。在最简频度的基础上，数据结构推出了大O记法，来表示算法程序的运行时间。
O(频度)
这里指的频度为最简频度
空间复杂度
他和时间复杂度类似，一个算法的空间复杂度也常用大O来表示：
要知道每一个算法所编写的程序，运行过程中都会占用不同大小的存储空间：
- 程序代码本身占用的存储空间
- 程序中如果需要输入输出数据，也会占用到一定的存储空间；
- 程序在运行过程中，可能还需要临时申请更多的存储空间。
首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。
程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。
事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。
举个例子：
int n;
scanf("%d", &n);
int a[10];
通过分析不难看出，这段程序在运行时所申请的临时空间，并不随 n 的值而变化。而如果将第 3 行代码改为：
int a[n];
此时，程序运行所申请的临时空间，和 n 值有直接的关联。
所以，如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：
- 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
- 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
- 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示； 在多数场景中，一个好的算法往往更注重时间复杂度，随着时间的推移，个人计算机的存储容量得到了显著的提升，一般的情况下，会做出拿空间换时间的操作，这样，我们就把空间复杂度控制在一个合理的位置就行了。