算法复杂度和大O表示法

概念

SICP算法复杂度是算法分析里的概念(对应到SICP里的增长阶),是衡量计算资源消耗数量(例如计算时间,存储器使用等)的指标。

算法的复杂度在理论上表示为一个函数:其定义域是输入数据的长度(通常考虑任意大的输入,没有上界),值域通常是执行步骤数量(时间复杂度)或者存储器位置数量(空间复杂度)。[……]

阅读全文

八皇后问题的Julia实现

问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?

尝试使用Julia实现一个回溯解:

julia-lang

实现

回溯法进行暴力查找:

很可惜,我[……]

阅读全文

对称加密、公钥加密和RSA

引子

对于加解密,我一直处于一种知其然不知其所以然的状态,项目核心部分并不倚重加解密算法时,可以勉强对付过去,一旦需要频繁应用诸如 AES/RSA等算法,这种状态就颇令人捉急了。

是时候了解一下原理了,所以找来了这本图解密码技术 给自己补补课:

图解密码技术

在该书深入浅出的指引下 ,补充了[……]

阅读全文

哈希函数

最近参加了一次面试,虽无笔试环节,几位考官却都在算法和思路题上大作文章,颇为受益

有这么几个问题印象深刻:

  1. 自创数据结构存储一些字符串,如何快速匹配用户输入(包含或者相等)?
  2. 若干memcached分布式的组成集群,有什么办法均匀的分布存储?
  3. 爬虫的排重怎么快又省(布隆过滤器原[……]

阅读全文