常用算法以及使用场景,实现

前言

任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。

算法必须具备三个特性:

时间复杂度计算

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则:总复杂度等于量级最大那段代码复杂度(如:多个循环最最大那个 n 5n n平方)、
  3. 乘法法则 嵌套代码复杂度等于嵌套内外代码复杂度乘积

常见复杂度量级

数组 连续内存地址,支持随机访问,增加,删除特定位置元素会造成,其他元素在数组中位置的移动。

链表 离散内存地址,不支持随机下标访问,因为会存储其他引用,索引占用内存会比数组多几倍,但是删除,增加操作的实际复杂度为O(1);

注意:

  1. 理解引用的含义
  2. 警惕指针丢失和内存泄露
  3. 利用哨兵简化实现难度
  4. 重点留意边界问题(链表为空;一个节点;两个节点;在处理头结点和尾节点的时候逻辑是否支持等情况;另外举例画图,辅助思考,多写多练)

有效的练习

  1. 单链表反转
  2. 链表中环的检测
  3. 两个有序的链表合并
  4. 删除链表倒数第几个节点
  5. 求链表的中间结点

数组和链表在功能上面来说可以代替栈,但是,数组和链表暴露太多接口,操作上的灵活会导致使用的不可控。用数组实现称为顺序栈,用链表实现称为链式栈 多用于先进后出,对称匹配 场景。

队列 特性为先进先出,也分为顺序队列和链式队列,主要使用场景为大部分资源有限的场景

递归 利:简化代码,增加可读性;弊:需要注意的是 堆栈溢出和重复计算的问题,还有时间,空间复杂度的问题

排序算法的执行效率分析:

  1. 最好情况,最坏情况,平均时间复杂度
  2. 时间复杂度系数,常数,低阶
  3. 比较次数和交换的次数(内存消耗,算法稳定性)

跳表 链表加索引的结构,跳表索引动态更新通过一个随机函数,决定要插入的节点插入到第几级索引当中

hash算法

散列表 通过键和值的结构存储数据

散列函数设计:

  1. 散列函数计算得到的散列值为一个非负整数
  2. 如果key1=key2,那么hash得到的值时相等的
  3. 尽量避免大量的hash冲突

hash冲突解决方案

多用于 存在,不存在去重等判断 场景

动态扩容

LRU缓存淘汰算法

二叉树存储方法:

二叉查找树

散列表和二叉树区别

平衡二叉树

翻转二叉树等例子

红黑树

AVL和红黑树随着树高度增加查询性能降低 AVL适合读多,更新,增加少场景 红黑树平衡查询和增加,删除场景

B树

是一种多路搜索树,下面m指的是m阶B树,为了进一步降低树的高度

无线多路的多路树又会导致结构退化成有序数组

文件系统和数据库索引都是存在硬盘的,如果数据量太大,不一定能一次性读取到内存。而通过每次加载B树的一个节点,然后一步步往下找

B+树

由于数据都在叶子节点,而且叶子节点之间还是用指针形成了链表,所以很适合使用像数据库这种根据条件查询多条记录的文档系统

B*树

B树 B+树 B*树小结:

B树 多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

B+树 在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点 中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

B*树 在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

递归树

堆排序和快速排序

  1. 堆排序数据访问方式没有快速排序友好,前者跳着访问的,对cpu缓存不友好
  2. 对于同样数据,在排序过程中,堆排序的数据交换次数要多于快速排序
  3. 推排序不是稳定排序
  4. 堆排序适用于动态数据排序(排行榜实时更新等),TOP K问题,优先级队列

搜索算法 大部分设计搜索的场景都可以抽象成图

广度优先搜索BFS

深度优先搜索DFS

遍历搜索所有路径,回溯,计算深度

字符串匹配算法

trie树与散列表,红黑树都可以实现字符串匹配的问题

假如我们要在主字符串A中查找字符模式串B。

BF算法

RK算法

BM算法

KMP算法

Trie树

AC自动机

AC自动机通过在Trie树上,加了类似KMP的next数组

贪心算法

动态规划

把一个复杂的问题转化成一个分阶段逐步递推的过程,从简单的初始状态一步一步递推,最终得到复杂问题的最优解

思路:

例子:爬楼梯,计算长方形最大面积,打家劫舍

回溯算法

一种选优搜索法,搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径

多出现在组合的问题中