[TOC]

大O表示法

  • log都指 $log_2$

  • 大O表示算法的速度有多快,但并不是以秒为单位的速度。而是操作数增加时,算法运行时间的增速。

  • 表示最糟糕情况下的运行时间

  • 除了最糟糕情况下运行时间,还有平均运行时间

  • 从快到慢的常用大O:

    • O(log n)
    • O(n)
    • O(n*log n)
    • O($n^2$)
    • O(n!)
  • 总时间和常量(固定时间量)有关。影响有时很大有时很小。

  • 平均情况和最糟情况,如快读排序可能因为基准数的选择而遇到最坏情况和最糟情况。

 二分查找的速度比简单查找快得多。
 O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。  算法运行时间并不以秒为单位。
 算法运行时间是从其增速的角度度量的。
 算法运行时间用大O表示法表示。

内存存储的基本方式 数组和链表

  • 两种最基本的数据结构——数组和链表

  • 观众席座位,写便签安排事件顺序表,上菜顺序

  • 数组 查询读取 随机访问

    • 数组在内存中是相连的
    • 不预留空间的话,增加新数据很麻烦,后面的都要向后挪。
    • 数组要事前申请一定的内存空间,但可能自己用不了,别人也不能用,浪费内存。
    • 超过申请空间大小,还是要挪。
    • 如果空间不够,可能会需要将整个数组全部复制到另一块内存中。
    • 数组知道每一个元素的地址,随机读取效率高,能迅速找到数组中的任何元素
  • 链表 插入 删除 顺序访问

    • 可以存储在内存任何地方,每一个元素存储了下一个元素的内存地址,从而串在一起。
    • 增加数据很容易
    • 删除元素很容易
    • 如果需要读取最后一个元素,需要从第一个元素开始访问,然后依次获取下一个元素的内存地址,直至访问到最后一个元素。
    • 需要读所有元素时,链表效率很高:读取第一个元素,然后根据地址读取第二个元素。
    • 如果需要跳跃,效率很低。
  • 数组下标索引从0开始

- 数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

O(n)=线性时间 O(1)=常量时间

链表删除时,只有能一次就访问到的时候时间才是O(1),链表能直接访问到底额元素是第一个元素和最后一个元素。

选择排序

 计算机内存犹如一大堆抽屉。

 需要存储多个元素时,可使用数组或链表。

 数组的元素都在一起。

 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。

 数组的读取速度很快。

 链表的插入和删除速度很快。

 在同一个数组中,所有元素的类型都必须相同(都为int、double等)。

递归

  • 递归和循环作用相同,递归更清晰。
  • 循环性能可能更好,递归可能更清晰

  • 递归要防止死循环

  • 基线条件->跳出递归 递归条件->递归调用自己

递归调用栈

  • 栈不能用于查找

  • 每调用一次方法,系统就会将该方法调用涉及的所有变量存储到内存中。

  • 调用栈可能会占用大量的内存,如果栈很高,可能意味着计算机存储了大量的调用栈这时:1.改用循环。 2.尾递归
  • 每个程序分配的栈空间有限,超出会引发栈溢出异常。

 递归指的是调用自己的函数。

 每个递归函数都有两个条件:基线条件和递归条件。  栈有两种操作:压入和弹出。

 所有函数调用都进入调用栈。

 调用栈可能很长,这将占用大量的内存。

分而治之-递归式问题解决方案

  • 土地分方块

原理:

  • 找出简单的基线条件
  • 确定如何缩小问题规模,使其符合基线条件

快速排序

  • 选一个基准,进行分区排序

 D&C将问题逐步分解。使用D&C处理列表时,基线条件很可能是空数组或只包含一个元 素的数组。

 实现快速排序时,请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。

 大O表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因所在。

 比较简单查找和二分查找时,常量几乎无关紧要,因为列表很长时,O(log n)的速度比O(n)
快得多。

散列表

  • 最有用的基本数据结构之一
  • 散列表的内部机制:实现、冲突和散列函数

散列函数

  • 不管给他什么数据,都返还给你一个数字 “将输入映射到数字”

  • 散列函数满足的要求:

    • 它必须是一致的。同样的额输入获得同样的数字。
    • 它应该讲不同的输入映射到不同的数字。这个数字为存储数组的下标,然而这样的函数几乎不可能写出。
  • 散列表用数组来存储数据,因此 获取元素的速度跟数组一样快

  • 散列函数知道数组有多大,只会返回合法的数组下标

  • 散列表里面由键和值组成,键被散列函数变为一个数字作为数组下标,这个下标的值就是值

  • 平均情况下,散列表的插入删除速度跟链表一样快,查找速度跟数组一样快。O(1)

  • 最糟情况下,散列表的这些速度都是 O(n)

  • 作用

    • 散列表被用于大海捞针式的查找 如DNS解析
    • 在插入数据前先查询,防止重复插入。速度非常快

 模拟映射关系;

 防止重复;

 缓存/记住数据,以免服务器再通过处理来生成它们。

冲突

  • 理想状态是 散列函数总是将不同的键映射到数组的不同位置。 但实际上,几乎不可能编写出这样的散列函数
  • 当多个数据分配到同一个下标的时候,就在这个下标上存储一个链表,
  • 散列函数很重要,如果链表很长,那么性能会急剧下降。好的散列函数不会产生很长的链表。

性能

  • 简单查找 O(n) 线性时间
  • 二分查找 O(log n) 对数时间
  • 散列查找 O(1) 常量时间

  • 避免冲突就能避开最糟情况:

    • 较低的填装因子
    • 良好的散列函数
  • 填装因子=元素数/位置数 可以理解为平均每一个位置要存多少个元素。填装因子<1,说明有空位。填装因子=1,则一个位置一个元素。填装因子>1,则一个位置不止一个元素。

  • 一般填装因子>0.7就考虑调整数组长度,减少填装因子。

  • 良好的散列函数就是散列函数尽量将不同的键映射到数组的不同位置,让数组中的值均匀分布

  • SHA函数

 你可以结合散列函数和数组来创建散列表。

 冲突很糟糕,你应使用可以最大限度减少冲突的散列函数。  散列表的查找、插入和删除速度都非常快。

 散列表适合用于模拟映射关系。

 一旦填装因子超过0.7,就该调整散列表的长度。

 散列表可用于缓存数据(例如,在Web服务器上)。

 散列表非常适合用于防止重复。

广度优先搜索 图算法

  • 图由节点和边组成,一个节点可能与多个节点直接连接,叫邻居

  • 广度优先搜索。找一个东西,朋友没有,从朋友的朋友找,从朋友的朋友的朋友找,直到找到

  • 先搜索一度关系,在搜索二度关系

  • 排队,先进先出

  • 有向图 无向图

最短路径算法(非加权图 段数最少)

  • 建立一个队列,先把一度关系加入队列中,然后从第一个人开始,查找不到就把这个人的二度关系加入队列,然后取出队列的第二个人开始搜索。直到找到或队列为空。
  • 避免重复检查,陷入死循环

  • 运行时间 = 人数加边数 =O(V+E) V为顶点 E为边数

  • 拓扑排序

 广度优先搜索指出是否有从A到B的路径。

 如果有,广度优先搜索将找出最短路径。

 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用广度优先搜索来
解决问题。

 有向图中的边为箭头,箭头的方向指定了关系的方向,例如,rama→adit表示rama欠adit钱。 无向图中的边不带箭头,其中的关系是双向的,例如,ross - rachel表示“ross与rachel约
会,而rachel也与ross约会”。

 队列是先进先出(FIFO)的。

 栈是后进先出(LIFO)的。

 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必
须是队列。

 对于检查过的人,务必不要再去检查,否则可能导致无限循环。

狄克斯特拉算法 加权图

  • 不能将狄克斯特拉算法用于包含负权边的图

最短路径算法(加权图 权重最少)

  • 这里重述一下,狄克斯特拉算法包含4个步骤。

    • (1) 找出最便宜的节点,即可在最短时间内前往的节点。
    • (2) 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销。
    • (3) 重复这个过程,直到对图中的每个节点都这样做了。
    • (4) 计算最终路径。(下一节再介绍!)
  • 每条边上的数字叫权重

  • 带权重的叫加权图 最短路径用狄克斯特拉算法
  • 不带数字的叫非加权图 最短路径用广度优先搜索

  • 两个节点互相指向对方,就成了一个环

  • 无向图中,每条边都是一个环
  • 狄克斯特拉算法只适用于有向无环图

实现狄克斯特拉算法

 广度优先搜索用于在非加权图中查找最短路径。

 狄克斯特拉算法用于在加权图中查找最短路径。

 仅当权重为正时狄克斯特拉算法才管用。

 如果图中包含负权边,请使用贝尔曼福德算法。

贪婪算法 贪婪策略

  • 贪婪算法优点:简单易行
  • 每步都采取最优的做法,每步都选择局部最优解,最终得打全局最优解
  • 易于实现,但并非都有效

  • 贪婪算法可以得到与正确解相近的解,而且更容易得到

  • 近似算法 获取精准解需要的时间太长时,可以使用。 优劣标准如下

    • 速度有多快
    • 得到的近似解与最优解的接近程度

NP完全问题

  • 旅行商问题 线路有n!条
  • 需要计算出所有解,并从中选出最小/最短的那个
  • NP完全问题 是以难解著称的问题

  •  元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。

  •  涉及“所有组合”的问题通常是NP完全问题。

  •  不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。

  •  如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题。

  •  如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。

  •  如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。


 贪婪算法寻找局部最优解,企图以这种方式获得全局最优解。

 对于NP完全问题,还没有找到快速解决方案。

 面临NP完全问题时,最佳的做法是使用近似算法。

 贪婪算法易于实现、运行速度快,是不错的近似算法。

动态规划

  • 动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当 每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用。

最长公共子串

  • 启示:
  •  动态规划可帮助你在给定约束条件下找到最优解。在背包问题中,你必 须在背包容量给定的情况下,偷到价值最高的商品。
  •  在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。

  • 贴士:

  •  每种动态规划解决方案都涉及网格。
  •  单元格中的值通常就是你要优化的值。在前面的背包问题中,单元格的值为商品的价值。
  •  每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网
    格的坐标轴。

  • 实际应用:

  •  生物学家根据最长公共序列来确定DNA链的相似性,进而判断度两种动物或疾病有多相 似。最长公共序列还被用来寻找多发性硬化症治疗方案。
  •  你使用过诸如git diff等命令吗?它们指出两个文件的差异,也是使用动态规划实现的。
  • 前面讨论了字符串的相似程度。编辑距离(levenshtein distance)指出了两个字符串的相 似程度,也是使用动态规划计算得到的。编辑距离算法的用途很多,从拼写检查到判断用户上传的资料是否是盗版,都在其中。
  •  你使用过诸如Microsoft Word等具有断字功能的应用程序吗?它们如何确定在什么地方断
    字以确保行长一致呢?使用动态规划!

 需要在给定约束条件下优化某种指标时,动态规划很有用。

 问题可分解为离散子问题时,可使用动态规划来解决。

 每种动态规划解决方案都涉及网格。

 单元格中的值通常就是你要优化的值。

 每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题。

 没有放之四海皆准的计算动态规划解决方案的公式。

K最近邻算法 (k-nearest neighbours,KNN)

  • 距离公式

  • 回归

  • 机器学习

  • 推荐系统

 KNN用于分类和回归,需要考虑最近的邻居。

 分类就是编组。

 回归就是预测结果(如数字)。

 特征抽取意味着将物品(如水果或用户)转换为一系列可比较的数字。 5  能否挑选合适的特征事关KNN算法的成败。

十一

  • 二叉查找树 平均查找时间为O(log n) 最糟为 O(n)
  • 最糟情况比有序数组要慢,但是二叉查找树的插入和删除速度很快
  • 二叉查找树不能随机访问 。如果二叉查找树处于平衡状态,那么平均访问时间也是 O(log n)

  • B树

  • 红黑树
  • 伸展树

反向索引

  • 一个散列表,将单词映射到包含它的页面 这种数据结构叫做反向索引 常用于创建搜索引擎

傅里叶变换

  • 如果能够将歌曲分解为不同的频率,就可强化 你关心的部分,如强化低音并隐藏高音。傅里叶变换非常适合用于处理信号,可使用它来压缩音 乐。

并行算法

  • 并行提升的速度并不是线性的,双核并行计算并不能让算法的速度提高一倍。因为
    • 并行性管理开销: 假设你要对一个包含1000个元素的数组进行排序,如何在两个内核之 间分配这项任务呢?如果让每个内核对其中500个元素进行排序,再将两个排好序的数组 合并成一个有序数组,那么合并也是需要时间的
    • 负载均衡: 假设你需要完成10个任务,因此你给每个内核都分配5个任务。但分配给内核 A的任务都很容易,10秒钟就完成了,而分配给内核B的任务都很难,1分钟才完成。这意 味着有那么50秒,内核B在忙死忙活,而内核A却闲得很!你如何均匀地分配工作,让两 个内核都一样忙呢?

MapReduce

  • MapReduce是一种流行的分布式算法,你可通过流行的开源工具Apache Hadoop来使用它。
  • 当并行算法只需要几个内核时,一台计算机就能运行了。如果需要大量的内核时,可让算法在多个计算机上运行。

  • 分布式算法非常适合用于在短时间内完成海量工作,其中的MapReduce基于两个简单的理 念:映射(map)函数和归并(reduce)函数。

    • 映射函数很简单,它接受一个数组,并对其中的每个元素执行同样的处理
    • 归并是将一个数组转换为一个元素

布隆过滤器和HyperLogLog

  • 给定一个元素,你需要判断它是否包含在这个集合中。为快速做出这种判断,可使用散列表。
  • 如果数据集很大,散列表很大,需要占用大量的存储空间,可以使用布隆过滤器。

  • 布隆过滤器是一种概率型数据结构。提供的答案有可能不对,但很可能说正确的。
  • 可能出现报错的情况,但不可能出现漏报的情况。有就一定有,但可能会找到错误的。没有就一定没有,不可能返回有。
  • 占用的存储空间很少,适合不要去答案绝对准确的情况。

  • HyperLogLog是一种类似于布隆过滤器的概率型算法,也不能给出准确答案,但占用存储空间少得多。

SHA 安全散列算法

  • SHA将一个字符串生成另一个字符串,然后根据生成的字符串生成数组索引,存储生成的字符串,索引说安全的。
  • 判断两个文件是否相同,计算SHA值
  • 检查密码。数据库存储散列值。
  • SHA-0,SHA-1,SHA-2,SHA-3,bcrypt

局部敏感的散列算法

  • SHA短发说局部不敏感的。这很安全,没法根据相似程度来破解
  • 局部敏感的意思是,如果两个字符串的差别很细微,那么生成的散列值的差别哦也很细微。
  • 局部敏感能通过比较散列值来判断两个字符串的相似程度。

  • Simhash是局部敏感的

Diffie-Hellman算法 密钥交换

  • 双方无需知道加密算法。不必会面协商要使用的加密算法
  • 要破解加密的消息比登天还难

  • 使用公钥和私钥。

  • 公钥是公开的,将其发布出去,别人向你发送消息时用公钥加密,然后自己受到消息用私钥解密,只有自己哟私钥,所以只有自己才能解密

线性规划

  • 用于在给定约束条件下最大限度地改善指定的指标。
  • 利润最大化