data structure and algorithm
我希望每个人对算法和数据结构是什么有一个深刻的认识，所以我们会在每一篇的文章的开始给你灌输下面的这些知识点：
1、数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以让你写出更漂亮更高效的代码（时间复杂度和空间复杂度）；
2、算法其实就是解决我们生活中遇到的问题的计算方法；
3、程序=数据结构+算法；要学好数据结构和算法就要在日常生活中把遇到的问题尝试用程序去解决
4、数据结构是实现一个算法的基础，所以想要学好算法，需要把数据结构学到位；
5、数据结构分为线性结构和非线性结构；线性结构的特点是数据元素之间存在一对一的线性关系；
6、线性结构又有顺序存储结构和链式存储结构两种的存储结构，顺序存储结构中存储元素是连续的，而链式存储结构中存储元素不一定是连续的；
度量一个算法执行时间的两种方法
1、事后统计的方法
这种方法是可行的，但是有两个问题，第一是想对设计的算法的运行性能进行评测，需要实际运行程序；第二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，运行时间会受这些因素的影响。这种方式，要在同一台计算机的相同状态下进行，才能比较哪个算法的速度更快。
2、事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优。
时间频度
时间频度：一个算法花费的时间与算法中语句的执行次数苏成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。
举例：计算1-100所有数字之和，有以下两个算法：
int total=0;
int end=100;
for(int i=1;i<=end;i++){
total+=i;
}
第一种算法的T(n)=n+1;
total=(1+end)*end/2;
第二种算法的T(n)=1;
时间复杂度
一般情况下，算法中的基本操作语句的重复执行次数是问题规模N的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数。则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为算法的渐进时间复杂度，简称时间复杂度（O(f(n))）；
在n趋向于无穷大的时候，我们可以忽略常数项、忽略低次项、忽略系数；
所以在对时间复杂度的计算中，T(n)不同，但时间复杂度可能相同；
计算时间复杂度的方法：
1、用常数1代替运行时间中的所有加法常数T(n)=n^2+7n+6 ==>T(n)=n^2+7n+1;
2、修改后的运行次数函数中，只保留最高阶项T(n)=n^2+7n+1 ==> T(n)=n^2;
3、去除最高阶项的系数T(n)=n^2 ==> T(n)=n^2 ==> O(n^2);
常用的时间复杂度
1、常数阶O(1)：无论代码执行了多少行，只要没有循环等复杂结构；
2、对数阶O(log2n)：在while循环中，每次都将i=2；类似的，O(log3n)则是每次都将i=3；
3、线性阶O(n)：一个单递增的for或者while循环；
4、线性对数阶O(nlog2n)：一个线性阶循环嵌套着一个对数阶循环；
5、平方阶O(n^2)：双重线性阶循环；
6、立方阶O(n^3)：三重线性阶循环；
7、K次方阶O(n^k)：k重线性阶循环；
8、指数阶O(2^n)：
常用的时间复杂度对用的图：
常见的算法时间复杂度由小到大依次为：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低；
平均时间复杂度和最坏时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间；
最坏情况下的时间复杂度为最坏时间复杂度，一般讨论的时间复杂度均为最坏情况下的时间复杂度；
空间复杂度
一个算法的空间复杂度为该算法所消耗的存储空间，它也是问题规模n的函数；
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序、归并排序和基数排序；
在做算法分析石，主要讨论的是时间复杂度。从用户使用体验上看更看重程序执行的速度，一些缓存产品金额算法（基数排序、递归）本质就是用空间换时间。