十大经典排序算法

0、算法概述0.1 算法分类十种常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。 0.2 算法复杂度 排序方法 时间复杂度(平均) 时间复杂...

Read more

蓄水池抽样算法(Reservoir Sampling)

一、问题给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,请问如何在只遍历一遍数据(O(N))的情况下,能够随机选取出m个不重复的数据。这个场景强调了3件事: 数据流长度N很大且不可知,所以不能一次性存入内存。时间复杂度为O(N)。随机选取m个数,每个数被选中的概率为m/N。 第1点限制了不能直接取N内的m个随机数,然后按索引取出数据。第2点限制了不能先遍历一遍,然后分块存...

Read more

加密算法、非对称加密算法和 Hash 算法

对称加密(Symmetric Cryptography),又称私钥加密对称加密是最快速、最简单的一种加密方式,加密(encryption)与解密(decryption)用的是同样的密钥(secret key),这种方法在密码学中叫做对称加密算法。对称加密有很多种算法,由于它效率很高,所以被广泛使用在很多加密协议的核心当中。对称加密通常使用的是相对较小的密钥,一般小于256 bit。因为密钥越大,加...

Read more