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)

时间复杂度(Time Complexity): 常用函数$T(n)$表示，指基本语句执行次数的数量级，通常用大O表示法(英文字母的大O,big-O)表示$T(n)=O(f(n))$.不包括这个函数的低阶项和首项系数，使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。比如$T(n)=2n^2+n+1=O(n^2)$，虽然具体的执行次数是2n^2+n+1，但是讨论时间的复杂度一般只讨论最高量级，即这里的$n^2$.

  1. 时间复杂度是一个量级的概念，，比如$O(fn(n^2+4n))$的量级是$n^2$，因为这个时间复杂度函数内最高量级是变量n的平方

  2. 基本语句: 所有语句中执行次数最多的那条语句。一个算法中所有语句频度之和与基本语句的频度之和是同一个数量级，比如$T(n)=2n^2+n+1=O(n^2)$，所有语句频度是2n^2+n+1，基本语句频度是n^2，它们是一个量级。

  3. 渐近时间复杂度（asymptotic complexity）：时间复杂度反映的是随着问题规模(n)的变大，计算所需的时间的增长速度，与系数的多少关系不大。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度$O(f(n))$，所以在算法分析时，往往对$T(n)$和$O(f(n))$两者不予区分，经常是将渐近时间复杂度$T(n)=O(f(n))$简称为时间复杂度。

常见时间复杂度的快慢比较：

  1. 时间复杂度由小到大：$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$(c是常数)

常见的时间复杂度有：

  • 常数阶$O(1)$

  • 对数阶$O(logn)$

    // 例子1
func algorithm(n int) {
    i := 1
    for i <= n {
        i = i * 2 // 基本语句频度是f(n),则2^f(n)<=n;f(n)<=log_2{n}
    }
    // T(n)=O(log_2{n})
}
// 例子2
func algorithm(n int) {
    i := 1
    for i <= n {
        i = i * 3 // 基本语句频度是f(n),则3^f(n)<=n;f(n)<=log_3{n}
    }
    // T(n)=O(log_3{n})
}
// 例子3
func algorithm(n int) {
    i := 2
    for i < n/2 {
        i = i * 2 // 基本语句频度是f(n),则2^f(n)<n/2;f(n)<log_2{n/2}<log_2{n}
    }
    // T(n)=O(log_2{n})
}

  • 线性阶$O(n)$

    // 例子1
func fact(n int) int {
    if n <= 1 {
        return 1
    }
    return n * fact(n-1)
    // n的阶乘，即执行n次乘法操作，故T(n)=O(n)
}
// 例子2
func algorithm(n int) {
    i, k := 1, 0

    for i < n-1 {
        k = k + 10*i
        i++ 
    }
    // 基本语句频度是k=k+10*i，共执行了n-2次，所以T(n)=O(n)
}

  • 线性对数阶$O(nlogn)$,

  • 平方阶$O(n^2)$

  • 立方阶$O(n^3)$

  • k次方阶$O(n^K)$,

  • 指数阶$O(2^n)$。

  • 阶乘阶$O(n!)$。

其他例子

// 例子1
func algorithm(n int) {
	y := 0
	for (y+1)*(y+1) <= n {
		y++
	}
	// (y+1)^2 <= n, n^0.5 >= y+1, 所以T(n)=O(n^0.5)
}

问题

  1. 对数阶为什么不指定具体的底数？因为底数不重要。比如有两个对数$log_2^N$和$log_3^N$，它们的比值为$log_2^N\over log_3^N$，运用换底公式后得：(lnN/ln2) / (lnN/ln3) = ln3 / ln2，ln为自然对数，显然这是个常数，与变量n无关，所以不同底数的对数函数所代表的时间复杂度在同一量级。

空间复杂度:若问题规模为n，f(n) 是算法运行过程中需要的辅助存储空间的函数，符号O表示取数量级的操作。用 S(n) 表示空间复杂度，则 S(n) = O(f(n)).

  1. 算法占用存储空间有三部分

    1. 存储程序本身的空间：比如具体的程序代码

    2. 存储算法输入和输出数据的空间：与问题规模n有关

    3. 对数据进行辅助操作的临时变量（也称辅助变量）所占存储空间：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序本身之外的辅助变量所占额外空间。分析算法的空间复杂度就是分析该部分的空间。

常见空间复杂度

  1. O(1)：若算法在运行过程中占用的临时空间为常数级别（即O(1)），则称算法是原地工作的

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

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

上界是指算法在最坏情况下的性能期望，即算法执行时间或所需资源不会超过这个界限，我们讨论算法的复杂度时，更多的是讨论上界，所以通常用上界来比较算法的效率；下界则是指算法在最好情况下的性能期望，即算法执行所需的最小时间或资源量, 算法的下界通常用于证明某算法无法更好地解决问题。平均指的是加权平均(?)。

算法的上下界表示：有的资料用$Θ(big-theta)、O(big-oh)、Ω(big-omega)$等表示，还有的是统一简单地用大O表示法$O(n)$来表示，其中n代表输入数据规模。 例如，在排序问题中，冒泡排序的下界是$O(n)$，意味着任何冒泡排序算法都至少需要执行n次比较操作，而快速排序，上界为$O(n^2)$。

算法的优化方向

  1. 用尽量少的执行步骤(运行时间)。

  2. 用尽量少的存储空间。

  3. 根据情况，空间换时间或者时间换空间。

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. 跟着书中说的网站来练习?

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

    2. 快速傅里叶变换

  8. 多项式的应用和表示

  9. noi

PreviousmathNext2.cryptology密码学

Last updated

Was this helpful?