大家都知道数据结构和算法不分家，提到数据结构就会想到算法，反之亦然。这是为什么呢？他们两者之间有什么奥秘呢？接下来带领大家走进数据结构和算法的世界。
定义
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构 = 元素 + 元素的关系
算法 = 对数据结构的操作
算法的效率
空间对效率的影响-空间复杂度
同样是输出从 1-10000 到数字，下面我们可以通过 for 循环和递归两种方式实现。
for 循环
public static void main(String[] args) { int a = 10000; for (int i=1;i<=a;i++) { System.out.println(i); } }
复制代码
执行完成，从 0-10000 输出。
代码中的 i 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
递归
public static void main(String[] args) { int a = 10000; aa(a); }
static void aa(int a){ a = a - 1; if (a > 0 ) { System.out.println(a); aa(a); } }
复制代码
打印到 4783，内存溢出
478547844783Class transformation time: 0.069511503s for 543 classes or 1.2801381767955802E-4s per class*** java.lang.instrument ASSERTION FAILED ***: "!errorOutstanding" with message transform method call failed at JPLISAgent.c line: 844*** java.lang.instrument ASSERTION FAILED ***: "!errorOutstanding" with message transform method call failed at JPLISAgent.c line: 844Exception in thread "main" java.lang.StackOverflowError
复制代码
递归情况下的空间复杂度：
该递归的空间复杂度为 S(n) = O(n)
结论：
解决问题的效率与空间的利用有关系。递归会占用更多的空间，导致内存溢出。
算法的巧妙程度对效率的影响-时间复杂度
计算：多项式的值
方法一：直接计算
无脑，不加思考，直接按照多项式计算。
public static void main(String[] args) { double[] a = new double[]{1,2,3}; System.out.println(f1(2,a,3)); System.out.println(f2(2,a,3)); }
//不思考，直接堆堆方法 static double f1(int n,double a[],double x){ long start = System.currentTimeMillis(); int i; double p = a[0]; for (i = 1;i <= n;i++){ p += a[i] * Math.pow(x, i); } long end = System.currentTimeMillis(); //计算执行时间 System.out.println(end - start + "ms"); return p; }
//使用公式堆方法 static double f2(int n,double a[],double x){ long start = System.currentTimeMillis(); int i; double p = a[n]; for (i = n;i > 0;i--){ p = a[i-1] + x*p; } long end = System.currentTimeMillis(); //计算执行时间 System.out.println(end - start + "ms"); return p; }
复制代码
执行结果都是 34。时间都是 0ms，因为执行时间太短
方法二的公式：
f(x)=a0+x(a1+x(...+x(an)))
代码如上面所示。
两种方法的执行效率
如何比较两者的执行效率呢，我们可以多执行几次核心方法就看到了，如下，执行了 10 的 7 次方，计算每次的执行时间再除以 10 的 7 次方：
public static void main(String[] args) { double[] a = new double[]{1,2,3}; f1(2, a, 3); f2(2, a, 3); }
//不思考，直接堆堆方法 static void f1(int n,double a[],double x){ long start = System.currentTimeMillis(); //重复执行10的7次方次 double flag = Math.pow(10, 7); for (int k = 1;k<=flag;k++) { int i; double p = a[0]; for (i = 1;i <= n;i++){ p += a[i] * Math.pow(x, i); } } long end = System.currentTimeMillis(); //计算执行时间 System.out.println((end - start)/flag + "ms"); }
//使用公式堆方法 static void f2(int n,double a[],double x){ long start = System.currentTimeMillis(); //重复执行10的7次方次 double flag = Math.pow(10, 7); for (int k = 1;k<=flag;k++) { int i; double p = a[n]; for (i = n;i > 0;i--){ p = a[i-1] + x*p; } } long end = System.currentTimeMillis(); //计算执行时间 System.out.println((end - start)/flag + "ms"); }
复制代码
执行结果：
结论：
算法的巧妙运用直接影响着执行的效率。第二个方法的执行效率要比第一个高一个数量级。
时间复杂度的渐进表示
上图
如下图是复杂度的感性认识，不同的函数随着 n 的增大，增幅不同。
折线图展示的比较直观，当我们在写了一个算法后发现复杂度较高一定要降到较低的复杂度的函数。
小窍门
关于复杂度计算总结了几个小窍门，如下：
1.若两段算法的复杂度相加取最大算法的复杂度为其复杂度，即
若T1(n)=o(f1(n))和T2(n)=o(f2(n))
T1(n)+T2(n)=max(o(f1(n)),o(f2(n)))
T1(n)∗T2(n)=o(f1(n))∗o(f2(n))
2.若算法是关于 n 的 k 阶多项式，则复杂度为 n 的 k 阶
3.for 循环的复杂度=循环次数*循环体的复杂度
4.if-else 结构的复杂度=max（条件判断复杂度，if 代码块复杂度，else 代码块复杂度）
小结
数据结构和算法学起来还是很上头的，本文旨在介绍数据结构和算法的关系（你中有我我中有你，缺一不可），以及通过小例子对算法的空间复杂度和时间复杂度的计算进行介绍和总结，通过比较时间复杂度和空间复杂度来判断什么是好的算法，我们在写算法的时候朝着什么方向去优化复杂度。
本文是数据结构和算法的开篇，接下来会有系列文章对数据结构和算法进行总结和介绍，敬请期待吧！
评论