AlgorithmStudy

极客时间-数据结构与算法之美的学习笔记

3.复杂度分析（上）

1.大O表示法：T(n)=O(f(n))，表示变化趋势

T(n)：代码执行的时间

f(n)：每行代码执行的次数综合

只取最大量级来表示：T(n)=O(2n²+2n+3)=>T(n)=n²

2.如何分析一段代码的时间复杂度

只关注循环次数最多的一段代码

总的时间复杂度等于量级最大的那段代码的时间复杂度

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

3.常见复杂度量级

多项式量级：

常量阶：O(1)
对数阶：O(logn)
线性阶：O(n)
线性对数阶：O(nlogn)
平方阶：O(n²)、立方阶：O(n³)、k次方阶：O(nk)

非多项式量级：

指数阶：O(2n²)
阶乘阶：O(n!)

4.复杂度分析（下）

1.最好情况时间复杂度

2.最坏情况时间复杂度

3.平均情况时间复杂度（加权平均时间复杂度/期望时间复杂度）

4.均摊时间复杂度（连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这时候就可以看是否能将较高时间复杂度那次操作的耗时平摊到其他那些时间复杂度比较低的操作上，一般平摊时间复杂度就等于最好时间复杂度）

5.数组：为什么很多编程语言中数组都从0开始编号

1.数组支持随机访问（a[i]_address=base_address+i*data_type_size），根据下标随机访问的时间复杂度为O(1)

2.数组与List的比较

List无法存储基本类型，只能使用包装类，有一定的性能损耗
数据大小事先已知，且用不到List提供的大部分方法时，可以用数组
当要表示多维数组时，往往数组比较直观
业务开发使用容器就可以，损耗一点点性能无伤大雅

3.为什么很多编程语言中数组都从0开始编号？

从0开始时a[k]内存计算：a[k]_address=base_address+k*data_type_size，从1开始编号时：a[k]_address=base_address+(k-1)*data_type_size，多了一次减法指令
历史原因：C语言设计者用0开始计数数组下标，之后的高级语言都效仿了C语言

6.链表（上）：如何实现LRU缓存淘汰算法

1.数组需要一块连续的内存空间来存储，当剩余空间大于申请值但是空间并不连续时也会申请失败

2.链表天然支持动态扩容

3.常见链表结构：单链表、双向链表、循环链表、双向循环链表

单链表：->data,next->data,next->data,next->NULL
- 每个节点都有data和后继指针next，尾节点指向NULL
- 插入删除复杂度0(1)，随机访问第n个元素需要从头到尾查找复杂度O(n)
循环链表
- 尾节点指针指向头节点
双向链表
- ->prev,data,next-><-prev,data,next-><-prev,data,next-><-prev,data,next

4.cpu在内存中读取数据的时候，会先把读取到的数据加载到cpu缓存中，而cpu每次从内存中读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块并保存到cpu缓存中，下次访问的时候会先从缓存中找，找到了就不用去内存中取，这样就实现了比内存访问速度更快的机制，而数组内存是连续的，所以在加载某个下标的元素时会把接下去的元素也加载进去，这样执行速度会比内存地址不连续的链表快

5.如果字符串是用单链表来存储的，怎么判断它是一个回文串？

快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到尾巴的时候慢指针就在中间点
慢指针在走的同时反转节点指向
再起一个指针和中间点的指针一次走并比较
时间复杂度O(n)，空间复杂度O(1)

7.链表（下）：如何轻松写出正确的链表代码

1.理解指针或引用的含义

2.警惕指针丢失和内存泄漏

3.利用“哨兵”简化实现难度

4.重点留意边界条件处理

5.举例画图，辅助思考

6.多写多练，没有捷径

7.5个常见的链表操作：单链表反转、链表中环检测、两个有序链表合并、删除链表倒数第n个节点、求链表的中间节点

8.栈：如何实现浏览器的前进和后退功能？

1.后进先出，先进后出

2.用数组实现的栈叫“顺序栈”，用链表实现的栈叫“链式栈”

3.空间复杂度是指除了原本的数据存储空间外，算法运行还需要额外的存储空间

4.用栈实现表达式求值：34+13*9+44-12/3，使用两个栈来实现，一个栈保存操作数，一个栈保存运算符，从左到右遍历，遇到数字压入操作数栈，遇到操作符就与操作栈顶元素比较，如果比栈顶元素优先级高，就将当前运算符压入操作符栈，当优先级低或者相同，从运算符栈顶取出运算符，从操作数栈顶取2个操作数进行计算，计算值压入操作数栈，继续比较

9.队列：队列在线程池等有限资源池中的应用

1.先进先出，入队enqueue()，出队dequeue()

2.数组实现的叫顺序队列，链表实现的叫链式队列

3.避免数据迁移可以使用循环队列，判断队列满的条件：(tail+1)%n=head

4.阻塞队列、并发队列

5.线程池的实现策略，在线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何实现

非阻塞的处理方式，直接拒绝任务
阻塞的处理方式，请求排队，等到有空闲线程时，取出队列的请求继续处理
- 基于链表实现无限排队的无界队列，会导致过多的请求排队等待，请求处理的响应时间过长不适合对响应时间敏感的系统
- 基于数组实现的有界队列，排队超过队列大小时，接下去的请求会被拒绝，适合对响应时间敏感的系统，设置一个合适的队列大小很重要

6.如何实现无锁并发队列？使用CAS（比较和交换（Conmpare And Swap））实现，入队前获取tail位置，入队时比较tail是否发生变化，如果否则允许入队，反之则入队失败，出队则是获取head位置，进行CAS

10.递归：如何用三行代码找到“最终推荐人”

1.递归需要满足三个条件

一个问题的解可以分解为几个子问题的解
这个问题与分解之后的子问题，除了数据规模不一同，求解思路完全一样
存在递归的终止条件

2.写递归代码要找到如何将大问题分解为小问题的规律，并基于此写出地推公式，再推敲终止条件，最终翻译成代码

3.递归弊端：堆栈溢出、重复计算、函数调动耗时多、空间复杂度高等

4.走台阶问题：总共n个台阶，每次可以走1个或者2个台阶，总共有多少种走法

第一步可以走1步或者2步，剩下(n-1)个台阶的走法加上剩下(n-2)个台阶的走法
递推公式：f(n)=f(n-1)+f(n-2)
终止条件为f(1)=1--走1步，和f(2)=2--走2个1步或者1个2步

int f (int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n+2);
}

11.排序（上）：为什么插入排序比冒泡排序更受欢迎

1.常见排序

排序算法	时间复杂度	是否稳定排序	是否原地排序
冒泡排序	O(n²)	✔️	✔️
插入排序	O(n²)	✔️	✔️
选择排序	O(n²)	❌	✔️
快速排序	O(nlogn)	❌	✔️
归并排序	O(nlogn)	✔️	❌
计数排序	O(n+k) k是数据范围	✔️	❌
桶排序	O(n)	✔️	❌
基数排序	O(dn) d是维度	✔️	❌

2.如何分析一个“排序算法”

排序算法的执行效率
- 最好情况、最坏情况、平均情况时间复杂度
- 时间复杂度的系数、常数、低阶
- 比较次数和交换（或移动）次数
排序算法的内存消耗
- 原地排序：特指空间复杂度为O(1)的排序算法
排序算法的稳定性
- 稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变称为稳定的排序算法，不然为不稳定的排序算法

3.冒泡排序

每次只会操作相邻的两个数据，一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作
优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作

//a表示数组，n表示数组大小
public void bubbleSort(int[] a ,int n){
	if(n<=1) return;
	for(int i=0;i<n;++i){
		for(int j=0;j<n-i-1,++j){
      //提前退出冒泡排序循环的标志位
      boolean flag =false;
      if(a[j]>a[j+1]){
        int tmp =a[j];
        a[j]=a[j+1];
        a[j+1]=a[j];
        //表示有数据交换
        flag=true
      }
    }
    //没有数据交换，提前退出
    if (!flag) break;
	}
}

冒泡排序只涉及相邻数据的交换，只需要常量级的临时空间，所以是原地排序算法，相邻两个数据相等时不交换，不改变顺序，所以是稳定的排序算法，最好时间复杂度为O(n)，最坏为O(n²)

4.插入排序

取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入

//a表示数组，n表示数组大小
public void insertionSort(int[] a,int n){
  if (n<=1) return;
  for (int i=1;i<=n;i++){
    int value =a[i];
    for(int j=i-1;j>=0;j--){
      if (a[j]>value){
        //移动数据
        a[j+1]=a[j];
      }else{
        //插入并退出当前循环
        a[j+1]=value;
        break;
      }
    }
  }
}

原地排序算法，稳定的排序算法，最好为O(n)，最坏为O(n²)

5.选择排序

原地排序算法，不稳定的排序算法，最好最坏都为O(n²)

6.冒泡排序与插入排序比较，冒泡排序需要k次交换操作，每次需要3个赋值语句，总共3*k单位时间，插入排序数据移动需要k个单位时间，所以一般用插入排序

12.排序（下）：如何用快排**在O(n)内查找第k大的元素

1.归并排序

原理：把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并（申请一个数组，比较两个前后两部分，当其中一部分全部放入了临时数组中的时候，再把另一个数组中的数据依次加入到临时数组末尾，最后把临时数组拷贝到原数组）在一起，这样整个数组就有序了
稳定的排序算法，最好最快平均时间复杂度都是O(nlogn)，空间复杂度O(n)，不是原地排序算法

2.快速排序

原理：排序下标p到r之间的一组数据，选择p到r中间的任意一个数据作为pivot（分区点），遍历p到r之间的数据，将大于pivot的放到右边，小于pivot的放到左边，将pivot放到中间，递归下标p到q-1之间的数据和下标q+1到r之间的数据，知道区间缩小为1，说明左右数据都有序了

不是稳定的排序算法，时间复杂度O(nlogn)，最差O(n²)

3.如何用快排**在O(n)内查找第k大的元素

选择数组区间A[0..n-1]的最后一个元素A[n-1]作为pivot，对数组A[0..n-1]原地分区，这样数组就分成了三部分A[0..p-1]、A[p]、A[p+1..n-1]，如果p+1=k，那A[p]就是要求解的元素，如果k>p+1，说明第k大的元素出现在A[p+1..n-1]区间，同理如果k<p+1，就在A[0..p-1]区间查找，再按上面思路递归

13.线性排序：如何根据年龄给100万用户数据排序

1.桶排序

原理：将要排序的数据分到几个有序的桶里，桶与桶之间有天然的大小顺序，每个桶里的数据再使用快排，排完之后桶与桶之间的数据不需要再进行排序
比较适合用在外部

2.计数排序

计数排序是桶排序的一种特殊情况
当排序n个数据，所处的范围并不大的时候，比如最大值为k，就可以把数据划分为k个桶，每个桶内的数据都是相同的，省掉了桶内排序的时间
计数排序只能用在数据范围不大的场景中，如果数据范围k比排序数据n大很多，就不适合用计数排序
是能给非负整数排序，如果是其他类型则需要再不改变相对大小的情况下转换为非负整数，比如[10.1,99.9]->[101,999]，[-1000,1000]->[1000,2000]

3.基数排序

以排序手机号为例，比较a,b两个手机号大小，如果在前面几位中a已经比b大了，后面几位就不用比了
每一位的比较都借助稳定排序算法，如果每次排序范围比较小，可以使用桶排序或计数排序来完成

14.排序优化：如何实现一个通用的、高性能的排序函数

1.优化快速排序，快排最坏时间复杂度为0(n²)，主要优化选取它的分区点

三数取中法：从区间的首、尾、中间分别取出一个数，然后对比大小，取这3个数的中间值作为分区点，如果数组比较大，可能要“五数取中”或“十数取中”
随机法：每次从要排序的区间中随机取一个元素作为分区点

15.二分查找（上）：如何用最省内存的方式实现快速查找功能

1.针对有序数据集的查找，分治**，时间复杂度O(logn)，只能使用数组，不能用链表，因为数组随机访问下标的时间复杂度是O(1)，链表是O(n)

2.二分查找的递归与非递归的实现

3.数据量太小不适合二分查找，只有数据量比较大，二分查找才会比较有优势。或者如果数据之间的比较操作比较耗时（比如存储的都是很长的字符串，比较会比较耗时），推荐使用二分查找，二分查找能尽可能减少比较次数

3.数据量太大也不适合二分查找，因为二分查找的底层依赖于数组，数组要求内存连续，数据很大时要求很大的连续内存空间，要求比较苛刻

vicedev/AlgorithmStudy