数据结构与算法——2.算法概述

这篇文章，我们来讲一下算法的概述，大致理解一下什么是算法。

目录

1.定义

2.生活实例

3.算法目标 

4.实际案例

4.1案例一

4.2案例二

5.小结

---

1.定义

官方解释：

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的的输出。

大白话：

根据一定的条件，对一些数据进行计算，得到需要的结果。

2.生活实例

3.算法目标 

在程序中，我们可以用不同的算法解决相同的问题，而不同的算法的成本也是不想同的。总体上，一个优秀的算法追求以下两个目标：

1. 花最少的时间完成需求
2. 占用最少的内存空间完成需求

4.实际案例

下面，我们体会并分析一些实际案例来领悟什么是算法。

4.1案例一

题目：计算1到100的和

方法一：

    public static void main(String[] args) {int sum = 0;int n = 100;for (int i = 0; i < n; i++) {sum += i;}System.out.println("sum="+sum);}

方法二：

    public static void main(String[] args) {int sum = 0;int n = 100;sum = (n+1)*n/2;System.out.println("sum="+sum);}

分析：

方法一需要完成以下几个动作：

1. 定义两个整型变量；
2. 执行100次算术运算（100次加法）；
3. 打印结果到控制台；

方法二需要完成以下几个动作：

1. 定义两个整型变量；
2. 执行3次算术运算（一次加法，一次乘法，一次除法）；
3. 打印结果到控制台；

很明显，方法二要比方法一好，因为方法一和二占用内存相同，但是方法二运算次数少，那么消耗的时间就少，那么它的性能就高，性能越高的算法就是越好的算法，就是算法所追求的。

4.2案例二

题目：计算10！

方法一：

public class Test {public static void main(String[] args) {long result = fun1(100);System.out.println(result);}public static long fun1(long n){if (n == 1) {return 1;}return n*fun1(n-1);  };
}

方法二：

public class Test {public static void main(String[] args) {long result = fun2(100);System.out.println(result);}public static long fun2(long n){int result = 1;for (int i = 1; i <=n ; i++) {result *= i;}return result ;};
}

分析：

方法一，使用了递归的解法，fun1方法会被执行10次，并且第一次执行未完毕，调用第二次执行，第二次执行也未完毕，调用第三次执行，，，，最终，最多的时候，需要在栈内存中开辟10块内存分别执行10个fun1方法，并且只有在第10个方法执行完成后，前面的方法才会一次执行完成，然后回收空间。这很浪费时间和空间。

方法二，使用for循环完成，fun2方法只会执行一次，只需要在栈内存中开辟一块内存，并且只需要运算10次，总体来说，内存开辟的少，运行次数少，算法更优。

很明显，方法二比方法一占用内存少，运行时间短，所以更好。

通过这两个例子，我们就能粗略的体会一下算法的思想了。

5.小结

这篇文章讲了算法的定义，举了生活中的例子，也讲了并且分析了具体的实例。主要目的就是让大家体会一下算法的思想，不求懂，但求有一点领悟。其实最重要的还是对具体问题的分析与解决。