感谢小码哥的 恋上数据结构，记录课程笔记。
什么是算法？
算法是用于解决特定问题的一系列的执行步骤。
以下算法是为了解决两数相加的问题：
// 计算a和b的和
public static int plue(int a, int b){
return a + b;
}以下算法是为了解决 n个数字的和 的问题：
// 1+2+3+...+n
public static int sum(int n){
int result = 0;
for(int i = 1; i <= n; i++){
result += i;
}
return result;
}使用不同算法，解决同一个问题，效率可能相差非常大。比如：
- 求第 n 个斐波那契数（fibonacci number）
如何评判一个算法的好坏？
如果单从执行效率上进行评估，可能会想到这么一种方案：
- 比较不同算法对同一组输入的执行处理时间
- 这种方案也叫做：事后统计法
上述方案有比较明显的缺点：
- 执行时间严重依赖硬件以及运行时各种不确定的环境因素
- 必须编写相应的测算代码
- 测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣：
- 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
- 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
- 空间复杂度（space complexity）：估算所需占用的存储空间
由于现在硬件发展的较好，一般情况下我们更侧重于时间复杂度。
下面代码是一个测试时间效率的小工具：
package com.mj;
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("-------------------------------------");
}
}大O表示法（Big O）
一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度。
忽略常数、系数、低阶：
- 9 >> O(1)
- 2n + 3 >> O(n)
- n^2^ + 2^n^ + 6 >> O(n^2^)
- 4n^3^ + 3n^2^ + 22n + 100 >> O(n^3^)
- 写法上，n^3^ 等价于 n^3
注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率。
对数阶的细节
对数阶一般省略底数：
- 由于 log~2~^9^ ∗ log~9~^n^ >> log~2~^n^，即每个对数基本都可以常数乘另一个对数
- 所以 O(log~2~^n^) 、O(log~9~^n^) 统称为 O(log^n^)
常见的复杂度
可以借助函数生成工具对比复杂度的大小： https://zh.numberempire.com/graphingcalculator.php
多个数据规模的情况
时间复杂度：O(n + k)
public static void test(int n, int k){
for(int i = 0; i < n; i++){
System.out.println("test");
}
for (int i = 0; i < k; i++){
System.out.println("test");
}
}LeetCode刷题指南
首先去 https://leetcode-cn.com/ 注册一个力扣账号。
我们以力扣上一道斐波那契的题目为例，顺便分析算法的时间复杂度。
题目网址：LeetCode: 509.斐波那契数
以执行 斐波那契数列(递归) 为例，必须写成这样：
斐波那契数列复杂度分析
斐波那契数列 - 递归
很简单的代码，相信来学数据结构的同学都能看懂。
// 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;
}
/*
// 也可以使用while循环
while (n-- > 1) {
second += first;
first = second - first;
}
*/
return second;
}力扣上执行：速度变快了，内存消耗还是很多....
开辟新的数组空间，用空间换时间。
public static int fib3(int n){
if(n <= 1) return n;
int[] fib = new int[n+1];
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i < fib.length; i++){
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}力扣上执行：呃，和上面好像没啥区别。。 
fib函数的时间复杂度分析
上面两种 fib 函数的差别有多大？
- 如果有一台 1GHz 的普通计算机，运算速度 10^9^ 次每秒，n 为 64
- O(n) 大约耗时 6.4 $*$ 10^-8^ 秒
- O(2^n^) 大约耗时 584.94 年
- 有时候算法之间的差距，往往比硬件方面的差距还要大
斐波那契的线性代数解法-特征方程
算法的优化方向
- 用尽量少的存储空间
- 用尽量少的执行步骤（执行时间）
- 根据情况：空间换时间、时间换空间
