|转载自：伯乐在线

|原文链接：https://github.com/kdn251/Interviews

|译文链接：http://blog.jobbole.com/110835/

算法

排序

快速排序

稳定：否

时间复杂度：

• 最优：O(nlog(n))

• 最差：O(n^2)

• 平均：O(nlog(n))

合并排序

合并排序是一种分治算法。这个算法不断地将一个数组分为两部分，分别对左子数组和右子数组排序，然后将两个数组合并为新的有序数组。

稳定：是

时间复杂度：

• 最优：O(nlog(n))

• 最差：O(nlog(n))

• 平均：O(nlog(n))

桶排序

桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序，或递归调用桶排序。

时间复杂度：

• 最优：Ω(n + k)

• 最差: O(n^2)

• 平均：Θ(n + k)

基数排序

基数排序类似于桶排序，将元素分发到一定数目的桶中。不同的是，基数排序在分割元素之后没有让每个桶单独进行排序，而是直接做了合并操作。

时间复杂度：

• 最优：Ω(nk)

• 最差: O(nk)

• 平均：Θ(nk)

图算法

深度优先搜索

深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。

时间复杂度：O(|V| + |E|)

广度优先搜索

广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。

时间复杂度：O(|V| + |E|)

拓扑排序

拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v 的边，u 的下标先于 v。

时间复杂度：O(|V| + |E|)

Dijkstra算法

Dijkstra 算法是一种在有向图中查找单源最短路径的算法。

时间复杂度：O(|V|^2)

Bellman-Ford算法

Bellman-Ford 是一种在带权图中查找单一源点到其他节点最短路径的算法。

虽然时间复杂度大于 Dijkstra 算法，但它可以处理包含了负值边的图。

时间复杂度：

• 最优：O(|E|)

• 最差：O(|V||E|)

Floyd-Warshall 算法

Floyd-Warshall 算法是一种在无环带权图中寻找任意节点间最短路径的算法。

该算法执行一次即可找到所有节点间的最短路径（路径权重和）。

时间复杂度：

• 最优：O(|V|^3)

• 最差：O(|V|^3)

• 平均：O(|V|^3)

最小生成树算法

最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之，最小生成树算法能在一个图中找到连接所有节点的边的最小子集。

时间复杂度：O(|V|^2)

Kruskal 算法

Kruskal 算法也是一个计算最小生成树的贪心算法，但在 Kruskal 算法中，图不一定是连通的。

时间复杂度：O(|E|log|V|)

贪心算法

贪心算法总是做出在当前看来最优的选择，并希望最后整体也是最优的。

使用贪心算法可以解决的问题必须具有如下两种特性：

• 每一步的贪心选择可以得到问题的整体最优解。

• 问题的最优解包含其子问题的最优解。

• 最优子结构

• 贪心选择

实例-硬币选择问题

给定期望的硬币总和为 V 分，以及 n 种硬币，即类型是 i 的硬币共有 coinValue[i] 分，i的范围是 [0…n – 1]。假设每种类型的硬币都有无限个，求解为使和为 V 分最少需要多少硬币？

硬币：便士（1美分），镍（5美分），一角（10美分），四分之一（25美分）。

假设总和 V 为41。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币，然后从 V 中减掉该硬币的值，如此重复进行。

• V = 41 | 使用了0个硬币

• V = 16 | 使用了1个硬币(41 – 25 = 16)

• V = 6 | 使用了2个硬币(16 – 10 = 6)

• V = 1 | 使用了3个硬币(6 – 5 = 1)

• V = 0 | 使用了4个硬币(1 – 1 = 0)

位运算

位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。

• 测试第 k 位：s & (1 << k);

• 设置第k位：s |= (1 << k);

• 关闭第k位：s &= ~(1 << k);

• 切换第k位：s ^= (1 << k);

• 乘以2n：s << n;

• 除以2n：s >> n;

• 交集：s & t;

• 并集：s | t;

• 减法：s & ~t;

• 提取最小非0位：s & (-s);

• 提取最小0位：~s & (s + 1);

• 交换值：x ^= y; y ^= x; x ^= y;

运行时分析

大 O 表示

• 大 O 表示用于表示某个算法的上界，用于描述最坏的情况。

小 O 表示

• 小 O 表示用于描述某个算法的渐进上界，二者逐渐趋近。

大 Ω 表示

• 大 Ω 表示用于描述某个算法的渐进下界。

小 ω 表示

• 小 ω 表示用于描述某个算法的渐进下界，二者逐渐趋近。

Theta Θ 表示

• Theta Θ 表示用于描述某个算法的确界，包括最小上界和最大下界。

以为这就结束了？No, 这些知识不仅仅是停留在理论，还有代码实现。

这其实是来自 GitHub 的一个 repo：https://github.com/kdn251/interviews

除了上述算法和数据结知识外，其中还有推荐了一些算法练习网站、视频教程、面试宝典、Google、Facebook 等知名公司面试题及解答代码。下载实例代码或者收藏练习网站。