• data-structure to implement algorithm
• My problem-set-of-algorithms

复杂度

时间复杂度

常数时间的操作

一个操作如果和样本的数据量没有关系 每次都是固定时间内完成的操作 叫做常数操作

时间复杂度为一个算法流程中，常数操作数量的一个指标,常用O（读作bⅰg O)来表示

具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N),那么时间复杂度为0(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”

算法流程按照最差情况来估计时间复杂度

master公式的使用

T(N)=a*T(N/b)+O(N^d)

1. log(b,a) > d ---> 复杂度为O(N^Iog(b,a))
2. log(b,a) = d ---> 复杂度为O(N^d*IogN)
3. log(b,a) < d ---> 复杂度为O(N^d)

对数器

1. 有一个你想要测的方法a
2. 实现复杂度不好但是容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
5. 如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b
6. 当样本数量很多时比对测试依然正确，可以确定方法已经正确。

比较器

1. 比较器的实质就是重载比较运算符
2. 比较器可以很好的应用在特殊标准的排序上
3. 比较器可以很好的应用在根据特殊标准排序的结构上

位运算

异或运算

1. 0^N=N , N^N =0
2. 异或运算满足交换律和结合率
3. 不用额外变量交换两个数
4. 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数
5. 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数

排序

选择排序

冒泡排序

插入排序

归并排序

1. 整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
2. 让其整体有序的过程里用了外排序方法
3. 利用master公式来求解时间复杂度
4. 归并排序的实质

时间复杂度O(N*IogN),额外空间复杂度O(N)

快速排序

不改进的快速排序

1. 把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：左侧<划分值、中间=划分值、右侧>划分值
2. 对左侧范围和右侧范围，递归执行

分析

1. 划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低
2. 可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为0(N^2)

随机快速排序（改进的快速排序)

1. 在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：左侧<划分值、中间=划分值、右侧>划分值
2. 对左侧范围和右侧范围，递归执行
3. 时间复杂度为0(N*IogN)

堆排序

see data-structure#Heap

堆排序

1. 先让整个数组都变成大根堆结构，建立堆的过程：
   1. 从上到下的方法，时间复杂度为0(N*IogN)
   2. 从下到上的方法，时间复杂度为0(N)
2. 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调
   整堆，一直周而复始，时间复杂度为0(N*IogN)
3. 堆的大小减小成0之后，排序完成

计数排序

基数排序

总结

排序算法的稳定性及其汇总

• 稳定性

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定
性的；否则就没有。

不具备稳定性的排序：
选择排序、快速排序、堆排序

具备稳定性的排序：
冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度O(N*\logN),额外空间复杂度O(1)，又稳定的排序。

常见的坑

1. 归并排序的额外空间复杂度可以变成O()，但是非常难，不需要掌握，有兴趣可以搜“归并排序内部缓存法”(会丧失稳定性 )
2. “原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成0(N^2)
3. 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”（会让空间复杂度变成O（N）)
4. 所有的改进都不重要，因为目前没有找到时间复杂度0(*|ogN),额外空间复杂度0(1)，又稳定的排序。
5. 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。

工程上对排序的改进

1. 充分利用O(N*IogN)和O(N^2)排序各自的优势(综合排序)
2. 稳定性的考虑(是否是基础排序)

二分

拜占庭

Now it's a question related to blockchain

拜占庭将军问题

（3n + 1）人 , 叛徒不超过 n ，（2n + 1）人能达成共识

数字签名 保证了只要有两人诚实这两人就能达成共识

异步拜占庭（克服了说假话后，又引入了不说话的难题

在节点可能失效的异步网络中，一致性和活性是不可能同时达成的

因为有了签名，如果指挥官是诚实的，指挥官以外的叛徒说假话并没有用，他们能够进行的恶意行为，只有不说话（不说话不会形成错误的共识 无害）。因此，拜占庭将军问题，其实又被简化成了“指挥官说假话”和“指挥官不说话的”的问题。

而这其中，指挥官不说话的问题，已经用例子说明了是个无解的问题——当然，如果这个问题有解，也违背了FLP和CAP。

于是只剩下一个问题——假设指挥官一定会下命令，而且每个人都知道这一点。那么指挥官说假话的时候，两个诚实的将军在异步系统里能不能达成共识？

不可能有任何一个人能收到超过k条和我不一致的消息了

假设有n个将军，f个将军是恶意的。n>=3f+1的条件下，弱中止条件下的拜占庭容错有解。

拜占庭将军问题可以说是拜占庭容错问题的特例——但两者的算法并不能直接相通，因为拜占庭将军问题相当于在拜占庭容错问题中，先假设能够对某个人成为指挥官这件事达成共识。多数情况下，拜占庭容错问题的解法都是基于拜占庭将军问题的解法，然后加上某些机制

算法PBFT（实用拜占庭容错），也介绍了它的消息复杂度是O(N^2)，即，想要对一条消息（一笔交易）达成共识，需要首先将消息广播给网络中的每一个节点（O(N)消息复杂度），然后为了防止恶意节点伙同恶意消息发布者故意在网络中散播假消息导致不一致，每一个节点需要再把自己收到的消息广播一遍，于是就有了O(N^2)的消息复杂度

恶意节点不拥有超过50%的算力时没法攻击比特币，然而，这里并没有考虑到时间t。也就是说，这里的50%是建立在诚实节点都在有效挖矿的基础上的。

对于比特币POW而言，从一开始就没有想过要避免无效挖矿的情况。它做的事情就是让无效挖矿损失的算力相比于所需要的总算力可以忽略，于是我们仍旧有接近50%的安全性。

在POW中，只有在最长链上挖矿才是有效挖矿，即，只有先同步最新的区块，即，同步所有交易，才能进行有效挖矿，而等到挖矿出了新区快，才能开始对于新区块的同步，也就是说这两个的关系是互相依赖的。