首页  思维导图  详情

算法

2020-11-11 10:20:11   0  举报





仅支持查看

AI智能生成

算法

作者其他创作

大纲/内容

按照算法思想归类

二进制的位操作

位操作，也叫作位运算

向左移位

逻辑左移

不存在，没什么意义

算术左移

将数字翻倍

向右移位

逻辑右移

不关心位变化，右移的时候补0

算术右移

>>>

算术右移时保持符号位不变

将数字除以 2 并求整数商

或

参与操作的位中只要有一个位是 1，那么最终结果就是 1

数字 53(110101) 和数字 35(100011) 的按位‘或’结果是 55(110111)

与

“与”的意思是，参与操作的位中必须全都是 1，那么最终结果才是 1

数字 53(110101) 和数字 35(100011) 的按位‘与’结果是 33(100001)

异或

也就是说如果参与操作的位相同，那么最终结果就为 0（假），否则为 1（真）

数字 53(110101) 和数字 53(110101) 的按位‘异或’结果是 0(0)

取余

同余定理

运用

hash算法

分页

迭代法

简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。

比如：f(x) = f(x-1)*2

具体应用

求数值的精确或者近似解

典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。

在一定范围内查找目标值。

典型的方法包括二分查找。

机器学习算法中的迭代。

K- 均值算法（K-means clustering）、PageRank 的马尔科夫链（Markov chain）、梯度下降法（Gradient descent）等等。

数学归纳法

观察数字的变化，总结出规律，证明规律

证明步骤

证明基本情况（通常是 n=1 的时候）是否成立；

假设 n=k−1 成立，再证明 n=k 也是成立的（k 为任意大于 1 的自然数）。

数学归纳法可以倒过来使用，就和动态规划很类似了

假设 n=k-1 的时候，问题已经解决（或者已经找到解）。那么只要求解 n=k 的时候，问题如何解决（或者解是多少）；

初始状态，就是 n=1 的时候，问题如何解决（或者解是多少）。

和使用迭代法的计算相比，数学归纳法最大的特点就在于“归纳”二字。它已经总结出了规律。只要我们能够证明这个规律是正确的，就没有必要进行逐步的推算，可以节省很多时间和资源。

递归调用的代码和数学归纳法的逻辑是高度一致的。数学归纳法经常使用递归来实现。也可以使用迭代法来实现。

递归

递归 vs 迭代

在某些场景下，递归的解法比基于循环的迭代法更容易实现。某些场景迭代比递归更好理解，看情况使用。

运用

穷举法

例子

奖励方式组合

分而治之

分而治之，我们通常简称为分治。它的思想就是，将一个复杂的问题，分解成两个甚至多个规模相同或类似的子问题，然后对这些子问题再进一步细分，直到最后的子问题变得很简单，很容易就能被求解出来，这样这个复杂的问题就求解出来了。

例子

归并排序

排列

从 n 个不同的元素中取出 m（1≤m≤n）个不同的元素，按照一定的顺序排成一列，这个过程就叫排列（Permutation）。当 m=n 这种特殊情况出现的时候，比如说，在田忌赛马的故事中，田忌的三匹马必须全部出战，这就是全排列（All Permutation）。

如果选择出的这 m 个元素可以有重复的，这样的排列就是为重复排列（Permutation with Repetition），否则就是不重复排列（Permutation without Repetition）。

运用

暴力破解密码

组合

从定义上来说，组合是指，从 n 个不同元素中取出 m（1≤m≤n）个不同的元素。例如，我们前面说到的世界杯足球赛的例子，从 32 支球队里找出任意 2 支球队进行比赛，就是从 32 个元素中取出 2 个元素的组合。

对于所有 m 取值的组合之全集合，我们可以叫作全组合（All Combination）。例如对于集合{1, 2, 3}而言，全组合就是{空集, {1}, {2}, {3}, {1, 2}, {1,3} {2, 3}, {1, 2, 3}}。

动态规划

通过不断分解问题，将复杂的任务简化为最基本的小问题，比如基于递归实现的归并排序、排列和组合等。不过有时候，我们并不用处理所有可能的情况，只要找到满足条件的最优解就行了。在这种情况下，我们需要在各种可能的局部解中，找出那些可能达到最优的局部解，而放弃其他的局部解。这个寻找最优解的过程其实就是动态规划。

状态转移

动态规划需要通过子问题的最优解，推导出最终问题的最优解，因此这种方法特别注重子问题之间的转移关系。我们通常把这些子问题之间的转移称为状态转移

状态转移方程

把用于刻画状态转移的表达式称为状态转移方程

运用

首先，如果一个问题有很多种可能，看上去需要使用排列或组合的思想，但是最终求的只是某种最优解（例如最小值、最大值、最短子串、最长子串等等），那么你不妨试试是否可以使用动态规划。

其次，状态转移方程是个关键。你可以用状态转移表来帮助自己理解整个过程。如果能找到准确的转移方程，那么离最终的代码实现就不远了。当然，最好的方式，还是结合工作中的项目，不断地实践，尝试，然后总结。

最小值

最大值

最短子串

最长子串

hash表

树

概念

树是没有简单回路的连通无向图。

有向树

有向树是一种特殊的树，其中的边都是有向的，而且它满足以下几个条件：

有且仅有一个结点的入度为 0，这个结点被称为根；

除根以外的所有结点，入度都为 1。从树根到任一结点有且仅有一条有向通路。

前缀树

前缀树是有向树的一个节点

前缀树/字典树

二叉树

红黑树

满二叉树

B+树

前序遍历

中序遍历

后序遍历

层次遍历

结点的高度

树的高度

深度优先搜索遍历

使用栈更加能节省内存

运用

查找单词

广度优先搜索/遍历

需要使用队列来维护实现

运用

人际关系的六度理论验证

广度优先策略可以帮助我们大幅优化数据分析中的聚合操作。聚合是数据分析中一个很常见的操作，它会根据一定的条件把记录聚集成不同的分组，以便我们统计每个分组里的信息。目前，SQL 语言中的 GROUP BY 语句，Python 和 Spark 语言中 data frame 的 groupby 函数，Solr 的 facet 查询和 Elasticsearch 的 aggregation 查询，都可以实现聚合的功能。

双向广度优先搜索

比单向广度优先搜索更加节省内存/cpu

如果双向的节点，如果双方分布很不均匀，这种情况不适合使用双向广度搜索。
单向广度优先搜索反而更好

缺点：解不一定是最优解

广度 vs 深度

广度优先搜索，相对于深度优先搜索，没有函数的嵌套调用和回溯操作，所以运行速度比较快。但是，随着搜索过程的进行，广度优先需要在队列中存放新遇到的所有结点，因此占用的存储空间通常比深度优先搜索多。

相比之下，深度优先搜索法只保留用于回溯的结点，而扩展完的结点会从栈中弹出并被删除。所以深度优先搜索占用空间相对较少。不过，深度优先搜索的速度比较慢，而并不适合查找结点之间的最短路径这类的应用。

图

分类

有向图

图里所有的边都是有向边

在有向图中，以结点 v 为出发点的边的数量，我们叫作 v 的出度。而以 v为终点的边之数量，称为 v 的入度。

无向图

一个图里所有的边都是无向边

混合图

既含有向边，又含无向边的图

通路

结点和边的交替序列组成的就是通路。所以，通路上的任意两个结点其实就是互为连通的。

回路

如果一条通路的起始点 v1 和终止点 vn 相同，这种特殊的通路我们就叫作回路。

深度优先搜索/深度优先遍历

使用栈更加能节省内存

广度优先搜索/广度优先遍历

需要使用队列来维护实现

运用

人际关系的六度理论验证

Dijkstra 算法

Dijkstra 算法的核心思想是，对于某个结点，如果我们已经发现了最优的通路，那么就无需在将来的步骤中，再次考虑这个结点。Dijkstra 算法很巧妙地找到这种点，而且能确保已经为它找到了最优路径。

Dijkstra 算法的主要步骤

贪心算法的一种

双向广度优先搜索

比单向广度优先搜索更加节省内存/cpu

缺点：解不一定是最优解

贪心算法

运用

Dijstra算法

时间复杂度/空间复杂度

时间复杂度

6 个通用法则

1. 四则运算法则

如果代码是平行增加的，就是加法。

如果是循环、嵌套或者函数的嵌套，那么就是乘法。

2. 主次分明法则

时间复杂度应该是 O(nlogn) + O(logn) + O(3)，但是和 O(nlogn) 相比，常量和 O(logn) 这种数量级都是可以忽略的，所以最终简化为 O(nlogn)。

例子，我们首先通过随机函数生成一个长度为 n 的数组，然后生成这个数组的全排列。通过循环，生成 n 个随机数的时间复杂度为 O(n)，而全排列的时间复杂度为 O(n!)，如果使用四则运算法则，总的时间复杂为 O(n)+O(n!)。
不过，由于 n! 的数量级远远大于 n，所以我们可以把总时间复杂度简化为 O(n!)。这对于空间复杂度同样适用。假设我们计算一个长度为 n 的向量和一个维度为 [n*n] 的矩阵之乘积，那么总的空间复杂度可以由 (O(n)+O(n2)) 简化为 O(n2)。

3. 齐头并进法则

参与比较的第一个字符串的长度 n 和第二个字符串的长度 m。代码使用了两次嵌套循环，第一层循环的长度是 n，第二层循环的长度为 m，根据乘法法则，时间复杂度为 O(n*m)。而空间复杂度，很容易从推导结果的状态转移表得出，也是 O(n*m)。

4. 排列组合法则

5. 一图千言法则

6. 时空互换法则

这里时空互换法则有个前提条件，就是计算量固定。而聚合操作的优化，是利用了广度优先的特点，大幅减少了整体的计算量，因此可以保证时间和空间复杂度都得到降低。

空间复杂度

按为了解决什么问题分类，
算法经验

整数

>>>

余数

查找