一定要认真听课，下课不复习！上课认真听讲是偷懒的最好方式！

恋上数据结构与算法（第一季）_哔哩哔哩_bilibili

目录

1 开发环境

2 斐波那契数

3 算法的评估

4 时间复杂度的估算

5 大O表示法

6 斐波那契数复杂度分析

7 leecode

1 开发环境

• eclipse或者IDEA（这里我是使用IDEA跟老师是不一样的）
• JDK 1.8的安装（这里是需要将相应的博客IDEA配置JDK的几种方式_匆不见勿的博客-CSDN博客_idea配置jdk）
• Main主方法

import java.util.List;

public class Main {
    

    
    public static int fib1(int n)
    {
        if(n <= 1) return n;
        return fib1(n-1) + fib1(n-2);
    }

    
    public static int fib2(int n)
    {
        if(n <= 1) 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;

    }


    public static void main(String[] args) {
       
        //测试方法二：
        //System.out.println(fib2(64));//速度很快
        Times.test("fib1", new Times.Task() {
            public void execute() {
                System.out.println(fib1(40));
            }
        });
        Times.test("fib2", new Times.Task() {
            public void execute() {
                System.out.println(fib2(40));
            }
        });
    }
}

• Times函数

  
  import java.text.SimpleDateFormat;
  import java.util.Date;
  
  public class Times {
  	private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
  	
  	public interface Task {
  		void execute();
  	}
  	
  	public static void test(String title, Task task) {
  		if (task == null) return;
  		title = (title == null) ? "" : ("【" + title + "】");
  		System.out.println(title);
  		System.out.println("开始：" + fmt.format(new Date()));
  		long begin = System.currentTimeMillis();
  		task.execute();
  		long end = System.currentTimeMillis();
  		System.out.println("结束：" + fmt.format(new Date()));
  		double delta = (end - begin) / 1000.0;
  		System.out.println("耗时：" + delta + "秒");
  		System.out.println("-------------------------------------");
  	}
  }
  

2 斐波那契数

• 斐波那契数：前面两个数进行相加，前面两个数是0和1，因此是0 1 1 2 3 5 8 13 
•  Main主方法

import java.util.List;

public class Main {
    

    
    public static int fib1(int n)
    {
        if(n <= 1) return n;
        return fib1(n-1) + fib1(n-2);
    }

    
    public static int fib2(int n)
    {
        if(n <= 1) 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;

    }


    public static void main(String[] args) {
       
        //测试方法二：
        //System.out.println(fib2(64));//速度很快
        Times.test("fib1", new Times.Task() {
            public void execute() {
                System.out.println(fib1(40));
            }
        });
        Times.test("fib2", new Times.Task() {
            public void execute() {
                System.out.println(fib2(40));
            }
        });
    }
}

• Times函数

import java.text.SimpleDateFormat;
import java.util.Date;

public class Times {
	private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
	
	public interface Task {
		void execute();
	}
	
	public static void test(String title, Task task) {
		if (task == null) return;
		title = (title == null) ? "" : ("【" + title + "】");
		System.out.println(title);
		System.out.println("开始：" + fmt.format(new Date()));
		long begin = System.currentTimeMillis();
		task.execute();
		long end = System.currentTimeMillis();
		System.out.println("结束：" + fmt.format(new Date()));
		double delta = (end - begin) / 1000.0;
		System.out.println("耗时：" + delta + "秒");
		System.out.println("-------------------------------------");
	}
}

3 算法的评估

• 对于不同的算法，不同的输出得到的时间是不同的，因此，很难去得到一个比较完美的算法。
• 算法评估：正确性、健壮性、可读性、时间复杂度（估算程序指令的执行次数）、空间复杂度（估算所需占用的存储空间）

4 时间复杂度的估算

• Eclipse之中的项目如何导入IDEA之中的方式见下面的微博：eclipse项目如何使用IDEA打开_Eric-x的博客-CSDN博客_idea打开eclipse项目运行，但是博主在引入的过程之中始终存在一个错误，如图所示，至今没有解决，所以我就是进行复制粘贴的方式进行验证的。
• 就是直接进行相应的复杂度的计算，例如下面的代码所示：

  	public static void test6(int n) {
  		// log5(n)
  		// O(logn) 这里的含义是与相应的log5
  		while ((n = n / 5) > 0) {
  			System.out.println("test");
  		}
  	}
  
  	public static void test7(int n) {
  		// 1 + 2*log2(n) + log2(n) * (1 + 3n)
  		//算下来就是相应的1 + 3*log2（n） + 3n*log2（n）
  		//外面进行相应的执行次数是2*log2（n）+1 注意：这里的1是特别的
  		for (int i = 1; i < n; i = i * 2) {
  			//计算次数：1 + 3n
  			for (int j = 0; j < n; j++) {
  				System.out.println("test");
  			}
  		}
  	}

5 大O表示法

• 大O表示法：常数项进行忽略，只保留相应高阶的部分
• 针对于对数的复杂度

   由于这个地方就是知识进行相应的一个没有常数项的一个选择，注意这里的大O表示法是一种估算，是一种粗略的分析模型，能够帮助我们在短时间内了解一个算法的执行效率。

• 常见的一些复杂度

• 针对于上面的复杂度，对于复杂度进行相应的对比，如下所示

• 数据规模比较小的时候，如下所示：

数据规模比较大的时候，如下所示：

• 空间复杂度的表示（更多的时候我们关心的空间复杂度）：

	public static void test2(int n) {
		// 运算时间为：1 + 3n 时间复杂度：O(n)
		// 由于这里只是定义了一个i，因此，这里的空间复杂度是1
		for (int i = 0; i < n; i++) {
			System.out.println("test");
		}
	}
public static void test10(int n) {
		//空间复杂度 O(n)
		int a = 10;
		int b = 20;
		int c = a + b;
		int[] array = new int[n];
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i] + c);
		}
	}

•  上面的java代码最终要变成相应的汇编指令。

6 斐波那契数复杂度分析

public class Main {
	
	
	// O(2^n)
	public static int fib1(int n) {
		if (n <= 1) return n;
		return fib1(n - 1) + fib1(n - 2);
	}
	
	// 时间复杂度O(n)
	public static int fib2(int n) {
		if (n <= 1) 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;
	}
}

• fib函数的时间复杂度分析上面就是对于每一层进行一个想加的过程。

• fib函数的时间复杂度分析上述说明了相应的算法的重要性。

• 算法的优化方向：较少的存储空间、较少的执行时间、时间换取空间、空间换取时间。

• 多个数据规模的情况：

7 leecode

• 算法题：https://leetcode.com/ https://leetcode-cn.com/