算法心得

介绍

以下知识来自于:

  • 普林斯顿在Coursera上面的algorithm网课
  • python算法书
  • 算法导论
  • 算法图解【一本书】

希望有朝一日能够继续学习。在上CS577的时候应该会更新这个文档

算法图解

算法简介

作为一个好的算法工程师,在对具体问题进行优化的时候,甚至要考虑使用插入排序还是堆排序…

二分查找居然是O(logn)时间…天哪,在我使用bisect的时候我一直以为是O(n),以为要走一遍。

大O表示法:

  • 表示的是「操作数
  • 用来描述的是「增速
    • 增速:算法的操作数,随着数据量增加的时间上升斜率
  • 防备的是「最差情况
    • 很多时候我们也要评估一下平均时间

一个O(n!)的例子:旅行商问题。

  • 给定五个城市,以什么样的顺序走一遍,所用的路程最短?

选择排序

数组因为元素都是挨在一起的,所以如果知道大小的话,最好事先安排好空间。

比较数组和链表:

  1. 数组的存储位置是连续的,链表没有要求
  2. 读取数据:数组支持「随机访问」,链表必须跑一遍。O(1) v.s. O(n)
  3. 插入数据:数组必须要移动插入位置之后的所有数据(如果地方不够还要把所有数据都挪一遍)链表只需要改地址。 O(n) v.s. O(1)
  4. 删除数据:数组必须要移动插入位置之后的所有数据,链表只需要改地址。 O(n) v.s. O(1)
  5. 所以如果是频繁插入,很少读取,那么应该用链表。
  6. 数组内部的元素类型必须都相同。

大O表示法一般会忽略前面的常数。

新的数据结构,关于Facebook如何存储用户名:

  • 有一个功能是判断当前用户名是否被注册。可以用二分法来寻找,这就需要支持随机访问。可以使用数组
  • 但是使用数组会带来一个问题,那就是当新用户注册完之后,需要把当前用户名插入进去,这一步就要挪动O(n)个数据,听起来太恐怖了。
  • 作者提出了个新想法:将A-Z分成24个不同的链表。而每个链表的头放在一个数组里
  • 这个方法告诉我们,其实数据结构并不是那几个定式,很多时候可以自由组合,特殊情况特殊对待。

递归

递归的一种替代法是将要执行的东西放入一个list中,一个挨一个的去执行,就像维持一个栈。

如果使用循环,程序的性能可能更高。如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

递归函数包含两部分:base case基线条件和recursive case递归条件。前者是针对的是什么时候函数不在调用自己。

栈的一个使用场景:讲一个栈顶的任务弹出,把其分为好多个小人物,重新压入栈顶。

调用栈:函数的调用使用的是调用栈

  • 调用另一个函数的时候,当前函数暂停并处于未完成状态。
  • 书中提到的盒子堆(栈)代替法其实是把递归函数的调用栈具象化了。
  • 当递归层数过多的时候,可以考虑尾递归优化。Python不支持尾递归优化,不过可以用知乎老哥的next和Trampline模拟出类似结果。

快速排序

分而治之的思路: Divide and Conquor

  1. 找到基线情况
  2. 如何将问题规模缩小,直到基线情况

快速排序(找pivot) v.s. 合并排序(两两分组 -> 四四分组 -> …):

  • 快速排序的最糟情况是O(n^2),但合并排序最糟情况也是O(nlogn),为何我们还用快排?
    • 因为其实运行时间是O(c * nlogn) 在n的函数不同的时候,常量一般影响不大。但是n的函数相近的时候,c这个常量就显得很重要了。而快排的c比合并的c小。所以平均情况下快排更好。
  • 快排每层操作都是n个元素,如果分的得当,一共会有logn层。

散列表 Hash Table

散列表将数据映射成索引——存储数据的列表索引

散列函数的要求:

  • 一致性:每次输入一个数据,返回的数字都相同
  • 最大可能防止冲突

散列表适用于「大海捞针似」的查找

散列表的应用:

  • DNS解析:将输入的网址转换成对应的IP地址,散列表是提供这种功能的方式之一。
  • 网页的缓存:大型互联网公司将一些主页什么的早早存在自己的服务器,而不是重复的生成同样的主页。

常量时间:并不意味着马上,而是说不管数据n多大,需要的时间都相同。【导数的含义】

关于冲突:

  • 冲突的一个简单的解决办法就是在对应的索引上面开一个新的链表。
  • 填装因子:总数据/位置总数。当填装因子 > 0.7的时候就要考虑整体迁移到一个更大的空间上了。虽然迁移很慢,但是平均下来速度还是O(1)。

广度优先搜索

在我所知道的算法中,图算法应该是最有用的。

一个节点可能与众多节点直接相连,这些节点被称为邻居

BFS解决两类问题:

  1. 路径存在与否?
  2. 路径是否最短?【如果单纯的以层数来划分的话…】

BFS包含了queue的结构,把第一层放进queue,一个一个取出。满足条件则停止,不满足条件则把新的candidate放在queue的最后。通常·,为了防止重复查找,我们会建立一个set来记录查找过的人。防止有两个点互相指着对方,则陷入无限循环。

BFS的运行时间:O(V+E) 每一条边E都要走, 每一个顶点V都会被放入queue一次。

拓扑排序: 比如说先刷牙才能吃饭,先打开电视才能看电视。打开电视和刷牙的顺序随意,但是看电视必不能在打开电视之前。【对这种问题,用BFS可以找到一个possible solution?不懂为何把这两个放在一起讲 】

树是一种特殊的图,没有指向前面的边。

狄克斯特拉算法

加权图中找最短距离。

基本思路:

  1. 找到目前可达的最短距离的点。
  2. 更新这个点的邻居们的距离。(如果多走一步其实更短的话)
    • 如果更新了的话,记得也更新表中的父节点。
  3. 将当前点从遍历中去掉,如果还有剩余点没有检查过,则返回1步。
  4. 从表中的终点开始,一步一步找父节点,输出最终路径。

如果有负权边的话,狄克斯特拉算法无法使用,可以用贝尔曼福特算法。

贝尔曼福特算法: 复杂度很大O(V*E)。思路是对边不停地进行松弛操作,

  • 第一步是出发点到所有点的一步最短距离,第二步是出发点到所有点的两步最短距离。
  • 因为出发点到终点,最多只要走n-1条边。所以第n-1步就可以结束了。
  • 如果途中包含了负环,些许尴尬。更新就无法停止了。

贪婪算法

对于NP完全问题,只能用近似算法来做。评估近似算法:

  1. 速度快不快
  2. 得到的近似解和最优解的近似程度

一些简易的判断是否为NP问题的方法:

  • 发现速度大概是O(n!)
  • 涉及「所有组合」
  • 不能将问题分成小问题
  • 涉及序列(旅行商)
  • 涉及集合(集合覆盖)
  • 如果问题可以转化成已知的NP问题(旅行商、集合覆盖)

动态规划

每次求解都可以画出一个表格:

  • 列从左到右分别是限制条件的越来越大
  • 行从上到下分别是增添进不同的元素
  • 方格里的元素就是要优化的对象
  • 有时答案出现在最后一列,有时候也可能是表中的极值
  • 当前方格的值常常取决于上一行的值(子问题可能是上面的行)
  • 各行的排列顺序与结果无关

动态规划不能处理的问题:

  • 比如说偷盗例子中,不能偷一个商品的一部分。背包剩40g地方,有100g的大米,动态规划只能处理0g/100g,无法处理只偷40g大米。可以考虑使用贪婪算法。
  • 处理的子问题无法相互依赖,也被称为离散子问题。

著名的费曼算法:

  1. 把问题写下来
  2. 仔细思考
  3. 把答案写下来

常见动态规划问题:

  • 最长公共子串
  • 最长公共子序列

其他

二叉搜索树的优点:插入删除元素需要的时间都是O(log(N))
其他的数据结构:B树、红黑树、堆、伸展树

并行算法的开销:

  1. 并行管理开销
  2. 负载均衡:不能一个机器忙得要命,一个机器闲着

布隆过滤器 & HyperLoglog:

  • 一种概率型数据结构。给出的答案有可能不对,但是很有可能是对的。很适合用于不要求答案绝对准确的情况。

SHA散列算法:

  • 默认局部不敏感(原文动一点,密文动好多),也可以用Simhash这种局部敏感的散列算法。
  • Diffie-Hellman密钥交换,优雅、不难理解并被广泛使用

线性规划:

  • 一个很宽泛的框架,图问题只是其中的一个子集
  • 使用复杂的Simplex算法

Backtracking 放弃法

backtracking(回溯算法)也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

“回溯”的具体意思就是将不可能解或者部分解的候选尽早的舍弃掉

深度优先算法DFS就是一种Backtracking的实例。

回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数,剪去一些不可能到达最终状态(即答案状态)的节点,从而减少状态空间树节点的生成。

遍历过当前节点后,为了回溯到上一步,要去掉已经加入到结果list中的当前节点。

  • 这一步有时候可以用list的append和pop实现

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。

  • 回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。
  • 而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。

https://blog.csdn.net/crystal6918/article/details/51924665

待做的题:

  1. N-Queens
  2. N-Queens II
  3. Combination Sum
  4. Combination Sum II
  5. Combination Sum III
  6. Permutations
  7. Permutations II
  8. Subsets
  9. Subsets II
  10. Palindrome Partitioning

Union Find

Union Find 是用来解决动态连通性(Dynamic Connectivity)问题的算法,是并查集的一种数据结构。

现在学的知识只能告诉我们是否联通,算法第二部分则会给出具体的联通路径。

API:Application Programming Interface 应用程序编程接口

等价性(Equivalence Relation):

  1. Reflexive: 自反性
  2. Symmetric:对称性
  3. Transitive:传递性

Dynamic Connectivity包含两部分:

  1. Find Query: 给定两个点,判断他们是否联通
  2. Union Command: 给定两个点,将他们联通(属于生成过程)

Quick Find

建立一个长度为n的列表,连通的点在列表中有着相同的元素。

Find: 当我们想知道p和q是否相通的时候我们只需要判断列表的第q和p位是否具有相同的数字即可。

Union: 将其中一个数字全部变为另一个。具体变的时候Union(a,b)我们将a位置的数字变为b位置的数字

Quick-Find 太慢啦!初始化需要跑完n, union操作需要跑完n, find操作需要1。

复杂度是n2n^2,我们不能接受这样的算法

Quadratic algorithm does not scale with technology.

Quick Union

建立一个树结构。还是一个长度为n的列表。每个位置对应的数值表示他的父亲节点是谁。

Find:只要p和q有相同的根节点就可以了

Union:将其中一个数字的根节点变成另一个数字的根节点的孩子节点。

Quick-Union 也不快!初始化需要跑完n, union操作需要跑完n, find操作需要n。

Weighted Quick Union

我们记录树的size,确保每次都将小树连接到大树的上面

每个根节点的深度不超过logn.初始化需要跑完n, union操作需要跑完logn, find操作需要logn。

Path Compression

在我们从一个节点回溯找根节点的时候,只要当前停留的节点不是根节点,我们就将这个节点指向根节点。压缩整个树的深度,因为就是深度才带来了时间的长度。

Summary

给定N个点,M个Union。在最极端的情况下:

Quick-Find Quick-Union Weighted QU QU+Path CP WQU+Path CP
MN MN N + M*logN N + M*logN N + M*log*N

Log* 是迭代对数函数

Applications——Percolation

很明显,概率越小越不容易渗透。

Phase Transition: 在能不能渗透的某个临界值p,图像会变得十分陡峭。

用蒙特卡洛模拟来找出临界值p:先给一个黑色方块。将其中的黑块一个一个的变成白块,直至渗透。

将每一个方块用一个点来表示。每次一个点亮的白块会call function 0~4次。
在第一行上面建立一个虚拟点,连接了第一行的每一个点。在最后一行下面建立一个虚拟点,连接最后一行的每一个点。反复判断这两个创建的虚拟点之间是否存在通路即可。

最后答案是0.592746

Analysis of Algorithms

观察法

Example: 3-Sum: Given N integers, how many triples sum to exactly zero?
Brute Force:三层for循环

很常见的一种画时间T和数据量N的图是log-log图。T=aNbT = aN^b

满足指数时间增长的算法可以通过一种方法检验:Doubling Hypothesis
用2N的时间除于N的时间来获得一个Ratio。如果这个Ratio趋近于一个常数,就说明差不多是指数增长(log(Ratio) = b),也可以画出log-log图然后进行拟合。

数学法

我们首先要记住一些基本操作的耗时。比如说分配一个长度为n的向量时间是O(n),连接两个字符串的时间也是O(n)

我们一般只算最耗时的那些步骤都被重复了多少次

所以在k-sum的例子中,最耗时的一步是CNkC_N^k这一步,O(nkn^k)

但是这种获得explcit的方式有点太难了,所以一般也不采用这种方法

Order Of Growth

1, log(N), N, Nlog(N), N^2, N^3, 2^N…

四种记号

Common mistake: Interpreting big-Oh as an approximate model.

内存使用

Stack & Queue

Stack: LIFO 后进先出
Queue: FIFO 先进先出
这两个都可以用linked-list / array来实现

Stack

Resizing Array

在Java实现中,我们需要用户给出array的默认长度。所以更灵活的,我们可以用resizing array。但是可变长度的array会有一个问题,那就是我们每向array末尾添加一个元素的时候,我们需要把之前所有元素都复制一遍,连同最新的元素放到一起。这样的话需要的操作为:1+2+3++N=N(N+1)/21+2+3+…+N = N(N+1)/2. 所以我们需要一个更简单的方法来做这个事情。

Repeated Doubling

Q. How to grow array?

A. If array is full, create a new array of twice the size, and copy items.

Cost of inserting first N items: N+(21+22+23++N)3NN + (2^1 + 2^2 + 2^3 + … + N) \sim 3N.

Q. How to shrink array?

A. halve size of array s[] when array is one-quarter full.

Stack considerations

Overflow and underflow:

  • Underflow: throw exception if pop from an empty stack.
  • Overflow: use resizing array for array implementation.

Null items:

  • We allow null items to be inserted.

Loitering:

  • Holding a reference to an object when it is no longer needed.
  • 解决方法是每次在pop之后,将不用的元素设为NULL

Linked-List or Resizing Array

如果我们希望总时间变少而不在乎单个插入/删除的操作时间的话,选择Resizing-Array。如果我们想避免某一个添加/删除很慢很慢的情况,选择Linked-List,因为每一步操作耗时基本是相同的。

Queue

Stack里面的push和pop在Queue里面被称为enqueue和dequeue

Generic

有时候元素不是数字或字符这么好操作的东西(Generic Type),就有点麻烦。在各个语言里面实现的时候,Liknked-List比Array更容易实现

Map

在Python里面是用dict来实现

The MutableMapping abstract base class, from Python’s collections module and discussed in the preceding pages, is a valuable tool when implementing a map.

Hash Table

Python的dict功能是用Hash Table实现的,因此查找才辣么快。

The novel concept for a hash table is the use of a hash function to map general keys to corresponding indices in a table.

The goal of a hash function, h, is to map each key k to an integer in the range [0,N − 1], where N is the capacity of the bucket array for a hash table.

If there are two or more keys with the same hash value, then two different items will be mapped to the same bucket in A. In this case, we say that a collision has occurred.

We say that a hash function is “good” if it maps the keys in our map so as to sufficiently minimize collisions. For practical reasons, we also would like a hash function to be fast and easy to compute.

The advantage of separating the hash function into two such components is that the hash code portion of that computation is independent of a specific hash table size. This allows the development of a general hash code for each object that can be used for a hash table of any size; only the compression function depends upon the table size. This is particularly convenient, because the underlying bucket array for a hash table may be dynamically resized, depending on the number of items currently stored in the map.

几种常见Hash编码方法

Treating the Bit Representation as an Integer

Python relies on 32-bit hash codes. If a floating-point number uses a 64-bit representation, its bits cannot be viewed directly as a hash code.(如果当前信息不超过32-bit,那么他本身就是编码后的hash-code)如果是64-bit可以用32+32/去掉其中一个32/两个32做异或

Polynomial Hash Codes

用Bit-representaion会出现的问题:The summation and exclusive-or hash codes, described above, are not good choices for character strings or other variable-length objects that can be viewed as tuples of the form (x0,x1,,xn1)(x_0,x_1,…,x_{n-1}), where the order of the x i ’s is significant.

An alternative hash code, which does exactly this, is to choose a nonzero constant, a = 1, and use as a hash code the value:

x0an1+x1an2++xn2a+xn1x_0a^{n-1}+x_1a^{n-2}+…+x_{n-2}a+x_{n-1}

By Horner’s rule (see Exercise C-3.50), this polynomial can be computed as:

xn1+a(xn2+a(xn3+...+a(x2+a(x1+ax0))))x_{n-1}+a(x_{n-2}+a(x_{n-3}+...+a(x_2+a(x_1+ax_0))))

We have done some experimental studies that suggest that 33, 37, 39, and 41 are particularly good choices for a when working with character strings that are English words.

Cyclic-Shift Hash Codes

A variant of the polynomial hash code replaces multiplication by a with a cyclic shift of a partial sum by a certain number of bits.

python里面的hash(x)可以计算一个x的hash值,However, only immutable data types are deemed hashable in Python. This restriction is meant to ensure that a particular object’s hash code remains constant during that object’s lifespan. Among Python’s built-in data types, the immutable int, float, str, tuple, and frozenset classes produce robust hash codes via the hash function. Instances of user-defined classes are treated as unhashable by default, with a TypeError raised by the hash function.

An important rule to obey is that if x == y, then hash(x) == hash(y).

Compression Functions

mapping the hash code integer into the range [0,N −1]. A good compression function is one that minimizes the number of collisions for a given set of distinct hash codes.

动态规划DP

分治方法将问题划为互不相交的子问题,递归的求解子问题,再将他们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题有公共的子子问题。在这种情况下,DP对每个子子问题只会求解一次,将其保存在一个表格中。动态规划常用来解决最优化问题

动态规划的四个步骤:

  1. 刻画一个最优解的结构特征
  2. 递归的定义最优解的值
  3. 计算最优解的值,通常采用自底向上的方法
  4. 利用计算出的信息构造最优解

计算一个p*q矩阵和一个q*r矩阵的成绩,需要计算p*q*r个标量乘法

钢条切割中每一个分段都是相同的,所有长度为k的钢条都属于一个子问题。但是矩阵链乘法每一个长度为k的子链都不相同,不属于一个子问题。

Numeric Optimization

Newton’s Method

算法

优点

  • fast convergence (under some condition)

缺点

  • Need second order derivative (二阶连续可导,为了防止出现切线斜率为0从而与x轴没有交点,如果此时找到了二阶导数为0的点,就是一个极值点)
  • Only 1-D

Gradient Descent

算法

优点

  • n-D
  • only need first order derivative

缺点

  • Speed depends
  • Rosenbrock函数效果不太好,出现锯齿状(jag)

Golden Section

算法

用secant line (割线) 代替 tangent line(切线)

优点

  • No derivative required
  • Fast

缺点

  • Only works on U-shape function. (可以考虑将一个大的函数切成几个小的U-shape部分)
  • 1-D

Nelder-Mead

算法

用一个三角形来估计切线

优点

  • n-D

缺点

  • converge slowly

排序算法

插入排序

数学基础知识

对称性+传递性无法推出自反性的例子:平行关系


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!