1.algorithm算法

一 概述

1 简介

目前主要是算法和《算法》这本书的笔记

1.3 他人评价

算法的中文译者:

1. 只有最后一章讲了一个比较深奥的Cook-Levin定理。不过说实在的我觉得作者并没有讲清楚，读者记住结论、领会精神也就好了。

朋友:

1. 算法的范畴非常大,主要有两种:处理业务流程的和处理事件的.前者是开发弄的,后者是研发弄的.

3 常识

3.1 算法的学习路线

1. 和算法联系最紧密的是数据结构.

2. 先熟悉基础的数据结构--数组和链表，然后是能一直用到的栈、队列等低级抽象数据类型，然后研究排序、搜索、图和字符串方面的基础算法.

3.3 排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

4 文档网址等

1. 算法复杂度，参考司马懿的回答，通俗易懂：https://www.zhihu.com/question/21387264

2. https://www.bigocheatsheet.com/：可以看到排序算法、时间复杂度等的总结图

三 基础

0 架构和常见词语

时间复杂度(Time Complexity)和空间复杂度(Space Complexity)和性能（待补充）

通常用大O表示法(英文字母的大O,big-O)分析算法的复杂度

时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度从小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)

参考司马懿的回答，通俗易懂：https://www.zhihu.com/question/21387264

常见的时间复杂度有： 常数阶O(1), 对数阶O(log2 n), 线性阶O(n), 线性对数阶O(n log2 n), 平方阶O(n^2)， 立方阶O(n^3) k次方阶O(n^K), 指数阶O(2^n)。

空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

一般讨论算法的性能时，主要都是关注时间复杂度，除非一些特别的算法--比如压缩算法，则是主要关注压缩率(当然也会考虑压缩用时)。

算法的上界（Upper Bound）和下界（Lower Bound）

上界是指算法在最坏情况下的性能期望，即算法执行时间或所需资源不会超过这个界限；下界则是指算法在最好情况下的性能期望，即算法执行所需的最小时间或资源量, 算法的下界通常用于证明某算法无法更好地解决问题。算法的上下界通常用函数$O()$表示，比如$O(n)$其中n代表输入数据规模。 例如，在排序问题中，冒泡排序的下界是$O(n)$，意味着任何冒泡排序算法都至少需要执行n次比较操作，而快速排序，上界为$O(n^2)$。

1 查找算法

1.1 顺序查找

1.2 二分查找

应用场景：

1. 在电话簿中查找名字以K打头的人

2. 在数据库中查找用户名

3. 有序数组中查找某个特定的数，用二分查找最快

prerequisites/preconditions:

1. 被查找的必需是一个有序的元素列表

原理：每次查找都可以排除一半的错误答案，所以效率不错，时间复杂度是$log2n$比如查找1~100中的某个数，最多只需要100/2=

实现：可以用递归也可以用非递归

实例分析：

1. 从旋转有序数组中查找目标值。思路如下:

   1. 首先判断中位数是不是查找目标，如果是就一发入魂。

   2. 然后要找到旋转点在中位数的左边还是右边

   3. 如果旋转点在右边，需要判断最左侧元素 <= 查找目标 < 中位数，如果true，则查找目标在中位数左侧，如果false，则查找目标在中位数右侧。它还有两个特点:

      1. 中位数以及它左侧的元素，全部是升序的。

      2. 最左侧元素，必定小于等于中位数。

   4. 如果旋转点在中位数的左侧，或与中位数重合，需要判断中位数 < 查找目标 <= 最右侧元素，如果true，则查找目标在中位数右侧，如果false，则查找目标在中位数左侧。它还有两个特点:

      1. 中位数以及它右侧的元素，全部是升序的。

      2. 最左侧元素，必定大于中位数。

性能：

1. TC是O(logN)

2 常见比较排序算法

常见排序算法可以分为两大类：

1. 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。比较类排序可继续分类:

   1. 交换排序

      1. 冒泡排序

      2. 快速排序

   2. 插入排序

      1. 简单插入排序

      2. 希尔排序

   3. 选择排序

      1. 简单选择排序

      2. 堆排序

   4. 归并排序

      1. 二路归并排序

      2. 多路归并排序

2. 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。非比较类排序可继续分类:

   1. 计数排序

   2. 桶排序

   3. 基数排序

2.1 交换排序

冒泡排序(Bubble Sort)

冒泡排序总的平均时间复杂度为O(n^2)。冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

快速排序(Quick Sort)

快速排序跟冒泡排序一样，也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。但是跟冒泡不同的是，它对冒泡排序进行了改进，采用了更有效率的分治法(Divide and Conquer)，基于一种叫做“二分”的思想，基本思路是：从已有的数据中随机选择一个数据mid，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比mid大，另外一部分的所有数据都要比mid小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。分而治之，各个突破。

应用场景：

1. 排序

2. 找出第k大的数

快速排序性能:

1. TC:最差时间复杂度和冒泡排序是一样的都是O(N^2)，最好的情况是O(NlogN)，它的平均时间复杂度为O(NlogN)，所以该排序方法被认为是目前最好的一种内部排序方法。

2. SC:

2.2 插入排序insertion sorting

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。时间复杂度为O(n^2)。是稳定的排序方法。

简单插入排序

希尔排序

2.3 选择排序

简单选择排序

一般流程：

1. 对于一个线性表（或其他）arr，从i=0开始

2. 寻找值最小的元素min，将其放到位置i处，i++

3. 循环第二步

性能:

1. 所以简单选择排序平均时间、最坏情况、最佳情况时间复杂度都为O（n^2）

2. 稳定

3. SC是O(1)

4. 简单选择排序没有利用上次比较的结果，所以造成了比较次数多，速度慢

树形选择排序（Tree Selection Sort）/锦标赛排序（Tournament Sort）

树形选择排序，又称锦标赛排序，是一种按照锦标赛思想进行选择排序的方法。它利用了上次比较的结果，是简单选择排序的改进。

基本思想：

1. 首先对n个记录的关键字进行两两比较，然后在其中n/2（向上取整）个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止，这个过程可以用一棵有n个叶子结点的完全二叉树表示。

2. 想选出次小者的话，可以应用上次比较的结果，从被之前最小值打败的节点中选择(这里)，如果这里有张图(!)的话可以看出，这个选择和完全二叉树的深度有关:含有n个叶子结点的完全二叉树的深度为log2N+1，则在树形选择排序中，除了最小关键字以外，每选择一个次小关键字仅需进行log2N次比较，因此，它的时间复杂度为O(nlogn)

性能:

1. 它的时间复杂度为O(nlogn)

2. 但是需要存储空间较多O(n)，并且需要和“最大值”进行多余的比较。

堆排序(heap sort)

操作主要分为两步：

1. 建堆

2. 堆化

应用场景：

1. 因为堆化其实就是选择出待排序序列中的最大值/最小值，所以它很适合top n/top k这样的场景，比如从N个数中选出最大的n个数。

性能：

1. TC：最好、最差、平均都是Nlog(N)

2. 不稳定

3. 缺点

   1. 相关的插入、删除操作比较快，但是在堆中搜索会很慢

和quick sort对比：

1. 堆排序的时间复杂度要比快速排序稳定，快速排序的最差的时间复杂度是O（n*n）,平均时间复杂度是O(nlogn)。堆排序的时间复杂度稳定在O(nlogn)。

2. 但是从综合性能来看，快速排序性能更好。

3. 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序

2.4 归并排序

二路归并排序

多路归并排序

3 常见非比较排序

3.1 计数排序

3.2 桶排序

3.3 基数排序

4 混合排序算法

4.1 Timsort(待整理)

Timsort是一种混合、稳定高效的排序算法，源自合并排序和插入排序，旨在很好地处理多种真实数据。它由Tim Peters于2002年实施使用在Python编程语言中。该算法查找已经排序的数据的子序列，并使用该知识更有效地对其余部分进行排序。这是通过将已识别的子序列（称为运行）与现有运行合并直到满足某些条件来完成的。从版本2.3开始，Timsort一直是Python的标准排序算法。如今，Timsort 已是是 Python、 Java、 Android平台 和 GNU Octave 的默认排序算法。

5 外部排序算法

5.1 败者树(loser tree)

五 经验

1 LeetCode

1. 如何正确高效地使用LeetCode？

   1. lucifer小哥哥的 leetcode题解，有中文分析和视频：https://github.com/azl397985856/leetcode,Repo 分为五个部分：

      1. 第一个部分是 leetcode 经典题目的解析，包括思路，关键点和具体的代码实现。

      2. 第二部分是对于数据结构与算法的总结。

      3. 第三部分是 anki 卡片， 将 leetcode 题目按照一定的方式记录在 anki 中，方便大家记忆。

      4. 第四部分是每日一题，每日一题是在交流群（包括微信和 qq）里进行的一种活动，大家一起解一道题，这样讨论问题更加集中，会得到更多的反馈。而这些题目可以被记录下来，日后会进行筛选添加到仓库的题解模块。

      5. 第五部分是计划， 这里会记录将来要加入到以上三个部分内容。

   2. 用动画的形式呈现解 LeetCode 题目的思路，尤其适合新手刷题使用:https://github.com/MisterBooo/LeetCodeAnimation

   3. fucking-algorithm:是一个总结 LeetCode 刷题思路和技巧的项目，该项目不是简单地刷题，而是帮你培养解题思维,https://github.com/labuladong/fucking-algorithm

2. LeetCode题解，151道题完整版
3. 算法珠玑——一个最精简的题库
4. https://github.com/pezy/LeetCode/tree/master/074.%20Sort%20Colors
5. https://leetcode.com/problems/sort-colors/description/
6. https://www.nowcoder.com/practice/4345e55fdb03498a89a97ec18e62b3ab?tpId=46&tqId=29103&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

2 实例

2.1 top n/top k问题

在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最好的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。例如，在搜索引擎中，统计搜索最热门的10个查询词；在歌曲库中统计下载最高的前10首歌等。

针对top K类问题，通常比较好的方案有这些：

1. 分治+Trie树/hash+小顶堆），即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树或者Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。

2. 快速排序:所谓的Top K问题其实就是找数组中最大的前k个值，所以，只要我们能够找到数组中的第k大值，那么Top K问题就会迎刃而解。

比如10亿个数中找出最大的10000个数:

1. 相对来说，这个问题建立最小堆比较好

2. 然后可以继续优化一下，把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。

3. 最后在剩下的100 * 10000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。

2.2 在海量数据中查找出重复出现的元素或者去除重复出现的元素

针对此类问题，一般可以通过位图法实现。例如，已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。 本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位，那么存储8位整数大约需要99MB。因为1B=8bit，所以99Mbit折合成内存为99/8=12.375MB的内存，即可以只用12.375MB的内存表示所有的8位数电话号码的内容。

2.3 n个无序数组中找第k大的数

1. 快速排序：O(N)

2. 冒泡:O(N*K)

3. 堆排序:内存中不能一次性存下很多数的时候，O(n)的算法就不能满足需求了，这时候有O(NlogK)的算法，即根据堆排序的思想，建立一个k的元素的大根堆，遍历整个数组，不断调整并输出。

四 高级

1 数学证明方法

1.1 数学归纳法(待整理)

六 问题

1 已解决

1.1 数组元素随机排序

使用洗牌算法(Fisher–Yates shuffle)

1.2 从零开始学数据分析，什么程度可以找工作？

做到以下几点:

1. 掌握基础的算法和数据结构:看看算法导论,去leetcode上刷题.常见的面试问题是字符串类、数组链表类和排序类题居多。

2. 掌握sql:常见sql函数等

3. 懂点统计学

2 未解决

1. 傅里叶变换

2. redundant topology

   冗余拓扑

七 未整理

1. 程序员十大基本算法：快速排序、最排序、归并排序、二分查找、BFPRT（线性查找）、DFS（深度优化）、BFS（过度优化搜索）、Dijkstra、动态规划、朴素贝叶斯分类

2. 经典排序算法总结：冒泡、快读、插入、希尔、归并、选择

3. serrch 编程中的算法

4. Codewalk: 生成任意文本：一个go实现的马尔可夫链算法
5. 排序的维基百科:https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#.E7.A9.A9.E5.AE.9A.E6.80.A7
6. 跟着书中说的网站来练习?

7. 1. 快速排序法的一般情形

   2. 快速傅里叶变换

8. 多项式的应用和表示

9. noi