1.说说你不知道的时间复杂度
一、为什么要学习数据结构和算法
其实，以前我们都会说，学习数据结构有多么多么的重要，长篇大论。这次，我们java程序员来看看数据结构和算法重要性。
例题：判断一个数是否是2的n次方。比如：2，4，8，16是2的n次方；6，10不是。
拿到这道题，用java的思路分析：
2：2
4：2*2
8：2 * 2 * 2
16：2 * 2 * 2 * 2
如果一个数除以2，最后余数是0，那么这个数就是2的n次方；如果余数是1，那么就不是。代码实现如下：
public static void main(String[] args) {
// 随意给一个数，判断这个数是不是2的n次方
int n = 16;
int yuShu = n%2;
int chuShu = n/2;
while (chuShu > 1) {
yuShu = chuShu % 2;
chuShu = chuShu / 2;
}
System.out.println( n + " 这个数" + (yuShu == 0?"是":"不是")+"2的n次方");
}但是，如果使用数据结构呢？下面来分析一下：将所有的十进制数字都转成2进制
2：10
4：100
8：1000
16：10000
他们的特点是什么呢？第一个数字是1，其余的都是0
而这几个数字之前的一个数字是什么呢？
1：01
3：011
7：0111
15：01111
他们的特点是什么呢？第一个是0，其余的都是1.
利用这两组数字，我们找规律，如果i和i-1按位&与的结果是0，就说明这个i是2的n次方；否则就不是
2 & 1 = 0
4 & 3 = 0
8 & 7 = 0
16 & 15 = 0
但是15 & 14呢，14的二进制数是01110，01111 & 01110 = 00001
所以，通过对数据的分析，我们可以用一句代码判断
if（n & (n=1) == 0) {
// 这个数就是2的n次方
} else {
// 否则不是
}二、数据结构概述
数据结构包括：线性结构和非线性结构
1、线性结构
1）线性结构是最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
2）线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表成为顺序表，顺序表中的存储元素是连续的
3）链式存储的线性表成为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
4）线性结构常见的有：数组、队列、链表和栈，后面我们会详细讲解
2、非线性结构
非线性结构包括：二维数组、多维数组、广义表、树结构、图结构
三、算法
算法有五个特征：有穷性，确定性，可行性，有输入，有输出
正确性，可读性，健壮性，bug（写出的代码bug少，而且系统稳定）
高效率与低存储：内存+CPU 堆栈内存 OOM
内存占用最小，CPU占用最小，运算速度最快。
评价算法的两个重要指标：时间复杂度 和 空间复杂度
时间复杂度：运行一个程序所花费的时间。
空间复杂度：运行程序所需要的内存。
1、 时间复杂度
1） 计算时间复杂度的意义：分析接口的性能
2） 时间复杂度表示方法：大写的O(n)表示，全称是O(nlogn)
3）常见的时间复杂度
计算时间复杂度，通常是计算比较大的，而且是不确定的的数。如果是已经确定的，那么就不用计算了，常量就是我们说的不用计算的一种。
> 常数：O(1) 1表示的是常数。不是循环的次数
比如下面的这个循环，时间复杂度是O(1)
public class BigO {
public static void main(String[] args) {
int n = 0; // 这句话的时间复杂度是O(1)
for (int i = 0; i < 3; i++) { // 这句话会执行4次, 它的时间复杂度也是O(1)
n = n + 1; // 这句话会执行3次, 他的时间复杂度也是O(1)
}
}
}> 对数：O(logn) 或 O(nlogn)
那么什么情况下会使用时间复杂度是对数的这种情况呢？来看一下下面的代码:
public static void time_log() {
int a = Integer.MAX_VALUE;
int i = 1;
while (i <= a) {
i = i * 2; // 这个循环一共要循环多少次呢?
// 我们来看看i的值2,4,8,16,32,64,128 2^0,2^1,2^2,2^3,2^4,2^5 ====> 2(n) = a ===> n = log2a
}
}这里i = i * 2 这句话需要循环多少次呢？其实我们要求的就是：循环多少次，i<= a 呢？2^n = a ; 求n=log2a, log以2为底a的对数。
以上是O(logn)的情况，那么什么情况下使用O(nlogn)呢？看下面的代码：
public static void time_nlogn() {
int a = Integer.MAX_VALUE;
int i = 1;
for (int j = 0; j < 10; j++) {
while (i <= a) {
i = i * 2; // 这个循环一共要循环多少次呢?
// 我们来看看i的值2,4,8,16,32,64,128 2(1),2(2),2(3),2(4),2(5) 2(n) = a ===> n = log2a
// 外面还有个j,所以就是(j * log2a)次
}
}
}只有while循环的时候，需要执行log2a次。那么外面多了一层for循环，这次要循环多少次呢？(j * log2a)次
> 线性：O(n)
线性指的就是O(n),也就是运行n次。
public static void time_on() {
int n = Integer.MAX_VALUE;
int a = 0;
for (int i = 0; i < n; i++) {
a = a + 1; // 这句话的时间复杂度是什么? O(n) n是几就运行几次. n是未知的,不确定的.如果n是确定的,就是常量了. 时间复杂度就是O(1)
}
}这里面a = a + 1;这句话会运行多少次呢？他和n有关系，如果n是10就运行10次，n是100就运行100次。有n决定，所以时间复杂度是O(n);
注意：这里的n是不确定的。如果n是确定的，那么时间复杂度就是O(1)le
> 线性对数：O(nlogn)
这个在上面已经说过了
> 平方：O(n ^ 2)
/**
* 时间复杂度O(n^2)
*/
public static void time_Onn() {
int n = Integer.MAX_VALUE;
int a = 0;
for(int i = 0; i < n; i++) {
for (int j = 0; j< n; j++) {
a = a + 1; // 这句话执行多少次呢?也就是说它的时间复杂度是多少呢? 外层循环执行n次,内层循环也是n次,所以最终执行n*n次,所以时间复杂度是O(n^2)
}
}
}这里有两层循环，外层循环执行n次，内存循环也是n次，所以代码a = a + 1；执行O(n*n)次。
常见的O(n^2)还有冒泡排序
public static void time_Onn2() {
int[] num = {3,6,1,0,8,5};
int n = num.length;
int a = 0;
for(int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
a = a + 1; // 这句话执行多少次呢?也就是说它的时间复杂度是多少呢? 来找找它的规律
/*
* 外层循环i=n, 内层代码执行1次
* 外层循环i=n-1,内层代码执行2次
* 外层循环i=n-2,内层代码执行3次
* 外层循环i=n-3,内层代码执行4次
* 外层循环i=1,内层代码执行n次
*
* 一共执行多少次呢? 0+1+2+3+......+n = n * (n+1)/2次
* 也就是冒泡算法的时间复杂度是O(n*(n+1)/2)次
*/
}
}
}冒泡排序的时间复杂度是多少呢？我们来分析一下：
外层循环i=n, 内层代码执行1次 外层循环i=n-1,内层代码执行2次 外层循环i=n-2,内层代码执行3次 外层循环i=n-3,内层代码执行4次 外层循环i=1,内层代码执行n次
一共执行多少次呢? 0+1+2+3+......+n = n * (n+1)/2次 也就是冒泡算法的时间复杂度是O(n*(n+1)/2)次。
在计算时间复杂度的时候去掉常数，所以就是O(n^2)
> N次方：
如果是三层循环，四层循环呢？那就是 n * n * n * n=n^4
上面的冒泡算法会执行n*(n+1)/2 = (n^2 + n)/2 ===>当有加减法的时候，这个时间复杂度怎么计算呢？ 取最大的就可以，这个最大是：首先去掉常数后，n2比n的阶层高，所以最后是O(n2)
4) 怎么计算时间复杂度？
第一步：找有循环的地方
第二步：找有网络请求的地方，包括RPC协议请求，数据库请求
网络请求可以通过打印日志来计算时间。
5） 常见时间复杂度的运行效率
O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^x) O(1)的运行效率是最高的。 所以，我们在优化的时候，目标是将所有的时间复杂度往O(1)进行优化。 实际上，O(1) > O(logn) > O(n) > O(nlogn) 效果都是很好的，几乎优化的空间不是很大。我们的最终目标就是将O(n^2) 和 O(n^x)往前优化。
- 案例1：
再来看看最开始的这个案例：判断一个数是否是2的n次方。比如：2，4，8，16是2的n次方；6，10不是。
如果一个数除以2，最后余数是0，那么这个数就是2的n次方；如果余数是1，那么就不是。代码实现如下：
public static void main(String[] args) {
// 随意给一个数，判断这个数是不是2的n次方
int n = 16;
int yuShu = n%2;
int chuShu = n/2;
while (chuShu > 1) {
yuShu = chuShu % 2;
chuShu = chuShu / 2;
}
System.out.println( n + " 这个数" + (yuShu == 0?"是":"不是")+"2的n次方");
}那么这段代码的时间复杂度是多少呢？log2n：log以2位底n的对数。O(logn)
后来通过二进制代码进行优化，优化后的结果是
if（n & (n=1) == 0) {
// 这个数就是2的n次方
} else {
// 否则不是
}这段代码的时间复杂度是O(1)。
我们优化以后，将O(logn)优化为O(1)了，效率大大提高了
- 案例2
比如，我们在看一段代码的时候，发现有性能瓶颈，然后这段代码使用的排序方式是冒泡排序，如何对这个排序进行优化呢？
找更优秀的替代排序方法，快速排序，归并排序，堆排序等。
2、空间复杂度
1）空间复杂度分析的意义
找出哪些地方花费内存多，哪些数据占用的内存开销大
2）如何找出程序的空间复杂度？
开空间的地方，比如：数组，链表，缓存Map，Set，队列Queue，递归等
数据结构和算法书籍推荐
