算法
- 算法是用于解决特定问题的一系列的执行步骤；
- 解决同一个问题，使用不同的算法，效果可能相差非常大；
斐波那契数列
- 下面通过一个实例来探索算法的复杂度，计算斐波那契数列的第n项；
- 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
- 此数列从第3项开始，每一项都等于前两项之和；
- 下面通过两种算法实现，根据下标(从0开始)计算斐波那契数列的第n项的值：
- 第一种算法：
/***
* 根据数列下标n,计算斐波那契数列第n项的值，下标从0开始
* 0 1 1 2 3 5 8 13 21 34 ...
* @param n
* @return 第n项的值
*/
public int fib_01(int n){
if (n < 2){
return n;
}
return fib_01(n-1) + fib_01(n-2);
}
- 算法思想：以递归的方式计算斐波那契数列第n项的值；
- 第二种算法：
public int fib_02(int n) {
if (n < 2) {
return n;
}
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
- 算法思想：循环计算第一个数与第二个数的和；
- 然后提供了一个工具类，专门又来测试这两种算法的耗时时间的，代码实现如下：
package com.example.myapplication.Tool;
import android.util.Log;
import java.text.SimpleDateFormat;
import java.util.Date;
public class TimeTool {
private static final SimpleDateFormat fmt = new SimpleDateFormat();
//定义一个Task接口
public interface Task{
void excute();
}
public static void check(String title,Task task){
if (task == null) return;
title = (title == null) ? "" : ("【" + title + "】");
Log.d("TimeTool",title);
Log.d("TimeTool","开始" + fmt.format(new Date()));
long begin = System.currentTimeMillis();
//算法任务执行
task.excute();
long end = System.currentTimeMillis();
double delta = (end - begin) / 1000.0;
Log.d("TimeTool","耗时" + delta + "秒");
Log.d("TimeTool","结束" + fmt.format(new Date()));
}
}
- 外界代码调用：
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
int m = 30;
TimeTool.check("fib_01", new TimeTool.Task() {
@Override
public void excute() {
Log.d("TimeTool",String.valueOf(fib_01(m)));
}
});
TimeTool.check("fib_02", new TimeTool.Task() {
@Override
public void excute() {
Log.d("TimeTool",String.valueOf(fib_02(m)));
}
});
}
- 当m = 30时，即计算斐波那契数列第30项的值，测试结果如下：
Snip20210327_57.png
- 看到算法一耗时0.039秒，算法二耗时0秒，可以忽略不计；
- 当m = 45时，测试结果如下：
Snip20210327_58.png
- 算法一的耗时明显比算法二的耗时长，随着m值的增大，两者之间的耗时差距会变得更大，从这里可以看出算法二优于算法一；
如何评判一个算法的好坏
- 正确性，可读性，健壮性；
- 时间复杂度：估算程序指令执行的次数(执行时间)；
- 空间复杂度：估算程序执行所需要占用的存储空间；
时间复杂度
- 时间复杂度一般使用
大O表示法来描述时间复杂度，它表示的是数据规模n对应的复杂度； - 在实际计算时间复杂度时，
会忽略常数，对数的底数，系数与低阶，因为随着n值的增大，时间复杂度与n的最高阶关系最大，其他的常数，对数的底数，系数与低阶可以忽略不计； - 大O表示法是
一种粗略近似的分析模型，是一种估算，能帮助我们在短时间内了解一个算法的执行效率；
常见的时间复杂度
- 常数阶：O(1)
- 对数阶：O(logn)
- 线性阶：O(n)
- 线性对数阶：O(nlogn)
- 平方阶：O(n^2)
- 立方阶：O(n^3)
- 指数阶：O(2^n)
- 时间复杂度的排列顺序为：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
- 函数图像如下所示：
Snip20210327_59.png
下面通过具体的实例代码来介绍常见的时间复杂度
- 时间复杂度的计算标准：程序指令的执行次数
【第一种】：常数阶：O(1)
public void test_01(int n){
//1
if (n > 10){
Log.d("MainActivity","n > 10");
}else if (n > 5){
Log.d("MainActivity","n > 5");
}else {
Log.d("MainActivity","n <= 5");
}
//1+4+4+4
for (int i = 0;i < 4;i++){
Log.d("MainActivity","test_01函数");
}
//总共:14
}
- 对于n的判断条件不计入在内，首先根据数值n，只会执行一条打印；
- for循环中 i = 0 只执行一次；i < 4，打印，i++都会执行4次；
- 总共执行步骤为 1+1+4+4+4 = 14；与n没有关系，所以时间复杂度属于常数阶：O(1)
【第二种】： 线性阶：O(n)
public void test_02(int n){
//1+n+n+n
for (int i = 0;i < n;i++){
Log.d("MainActivity","test_02函数");
}
//总共:3n+1
}
- for循环 i = 0执行一次，i < n，打印，i++ 都会执行n次，总共执行步骤为：(3n+1)
- 其中系数3与常数1可以忽略，所以时间复杂度属于：线性阶：O(n)
- 单层for循环。
【第三种】： 对数阶：O(logn)
public void test_05(int n){
while ((n = n/2) > 0){
Log.d("MainActivity","test_05函数");
}
//总共:log2(n)
}
- 当n = 16时，每次将n/2，满足条件，执行打印步骤；n依次取值为8，4，2，1，0，前面四次满足条件执行打印，可以看出执行次数x满足2^x=16；所以x=log2(n)
- 底数可以省略，所以时间复杂度属于：对数阶：O(logn)
【第四种】：线性对数阶：O(nlogn)
public void test_07(int n){
//外层:1+2n
for (int i = 0;i < n;i++){
int j = 1;
//内层:1+log2(n)
while (j < n){
j = j * 2;
}
}
//总共:(1+2n)+n*(1+log2(n))=n*log2(n)+3n+1
}
- 外层循环： i = 0 执行一次，i < n，i++ 分别执行n次，总共执行1+2n；
- 内层循环： j = 0 执行一次，while循环本质与上述的对数阶相同 会执行log2(n)，总共执行 n * (1+log2(n))；
- 总共执行 1+2n + n * (1+log2(n)) = nlog2(n)+3n+1；系数，底数，低阶，常数全部忽略只剩nlogn，所以时间复杂度属于：线性对数阶：O(nlogn)
【第五种】：平方阶：O(n^2)
public void test_03(int n){
//外层:1+n+n
//内层:n*(1+n+n+n)
for (int i = 0;i < n;i++){
for (int j = 0;j < n;j++){
Log.d("MainActivity","test_03函数");
}
}
//总共:(1+2n)+n*(1+3n)=3n^2+3n+1
}
- 外层循环：i = 0执行一次，i < n，i++分别执行n次，总共执行1+2n
- 内部循环：j = 0执行一次 i < n，打印，i++分别执行n次，总共执行n*(1+3n)
- 总共执行：(1+2n)+n*(1+3n)=3n2+3n+1，忽略系数，低阶，常数，所以时间复杂度属于平方阶：O(n2)
【第六种】：立方阶：O(n^3)
- 平方阶是两层for循环，那么立方就是三层for循环，这里就不举例说明了；
【第七种】：指数阶：O(2^n)
- 上面计算斐波那契数列的第n项值的第一种算法就能属于指数阶：O(2^n)；下面我们来详细分析一下：
public int fib(int n){
if (n < 2){
return n;
}
return fib(n-1) + fib(n-2);
}
- 代码实现中存在递归调用，假设n = 5时，下面是调用流程图；
Snip20210327_61.png
- fib函数总共调用次数为：2^0 + 2^1 + 2^2 + 2^3 = 2^4-1 = 2^(5-1) - 1 = 2^(n-1)-1 = 0.5 * 2^n -1；系数，常数忽略，所以时间复杂度为：指数阶：O(2^n)
- 对于计算斐波那契数列的第n项值的第二种算法：
public int fib_02(int n) {
if (n < 2) {
return n;
}
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
- 单层for循环，所以其时间复杂度为
线性阶O(n)；
算法优化的方向
- 用尽量少的存储空间；
- 用尽量少的执行步骤(执行时间);
- 根据实际情况可以：
- 空间换时间；
- 时间换空间；
多个数据规模的情况
public void test_08(int n,int k){
for (int i = 0;i < n;i++){
Log.d("MainActivity","test_08");
}
for (int i = 0;i < k;i++){
Log.d("MainActivity","test_08");
}
}
- 其时间的复杂度为O(n+k)；
