博客

当某些问题不能用贪心算法来解决的时候，我们可以考虑动态规划。动态规划的思想类似于分治，探索所有可能的解，然后把问题分解成一系列子问题，然后为越来越大的子问题构筑正确的解。

加权的区间调度问题

我们有n个请求，标记为1,2,…,n。每个请求i指定了开始时间s_i和结束时间f_i。每个区间i也有一个值，即权重v_i。如果两个区间不重叠，那么它们是相容的。求一个彼此相容的子集，是所选区间的值的总和最大。

定义p(j)，表示区间j中最大的序标i<j，使得区间i和j不相交。就是i是在j开始前结束的，左边最近的区间。
定义OPT(n)是最优解，则：
OPT(j) = max(vj+OPT(p(j)),OPT(j-1))

一个记录了中间计算结果的算法：
M-Compare-Opt(j)
  If j=0 then
    Return 0
  Else if M[j]不为空 then
    Return M[j]
  Else
    定义M[j]=max(vj+M-Compare-Opt(p(j)), M-Compare-Opt(j-1))
    Return M[j]
  Endif

分段最小二乘

用尽可能少的线段来拟合二维平面上的点。给定一组点P={(x₁,y₁), (x₂,y₂),…,(x_n,y_n)}。我们用p_i来表示点(x_i,y_i)。首先把P分成若干段，每个段是P的子集，表示一组连续的坐标。对于P中划分的每个分段S，计算出相对于S中的点的误差最小的线。定义划分的penalty为以下项之和：
(i)P划分的段数乘以固定的给定乘数C>0;
(ii)对于每个段，穿过该段的最优线的误差值

如果最优划分的最后一段是pi,...,pn，那么最优解的值就是OPT(n)=ei,n+C+OPT(i-1)
对于点p1,...pj上的子问题OPT(j)=min1≤i≤j(ei,j+C+OPT(i-1))

Segmengted-Least-Squares(n)
  数组M[0...n]
  置M[0]=0
  For 所有的对 i≤j
    为分段pi,...pj计算最小方差ei,j
  Endfor
  For j=1,2,...,n
    使用递归OPT(j)公式来计算M[j]
  Endfor
  Return M[n]

Find-Segmnets(j)
  If j=0 then
    不输出
  Else
    找到一个i使得ei,j+C+M[i-1]最小
    输出分段{pi,...pj}和Find-Segments(i-1)的结果
  Endif

子集和问题

在考虑调度问题中，有一台可以处理作业的机器，以及一组请求{1，2，…,n}。对于某个数W，我们只能在时刻0和时刻W期间内使用该资源。每个请求对应于一个作业，处理它需要时间w_i。我们希望选择一个子集S，使得S中作业的总时间≤W，并且尽可能大。

如果w<wi，那么OPT(i,w)=OPT(i-1,w)；否则
    OPT(i,w)=max(OPT(i-1,w), wi+OPT(i-1,w-wi))

Subset=Sum(n,W)
  数组M[0...n, 0...W]
  对每个w=0,1,...,W，初始化M[0,w]=0
  For i=1,2,...,n
    For w=0,...,W
      利用递归OPT(i,w)公式来计算M[i,w]
    Endfor
  Endfor
  Return M[n,W]

算法的时间复杂度为O(nW)

背包问题也可以用类似的方法来递归解决

RNA二级结构（略）

序列对比

如何定义两个字符串之间的相似性？假设给定两个字符串X和Y，其中X是由符号序列x₁x₂…x_m组成，Y是由符号序列y₁y₂…y_n组成。匹配(matching)是一组有序对，其性质是每个项最多出现一对。如果不存在交叉对，那么这两个集合中的匹配M是一个比对(alignment)。我们对相似性的定义将基于找到X和Y之间的最优比对。假设M是X和Y之间的给定比对。
(i)存在一个参数δ>0，它定义了空隙罚分(gap cost)。对于在m中不匹配的X或Y的每个位置（空隙），产生δ的开销
(ii)对于字母表中没对字母p和q，存在用q对齐p的不匹配开销(mismatch cost)，记为α_pq。通常假设每个字母p的α_pp=0
(iii)M的开销是其空隙开销和不匹配开销的总和，我们寻求最低开销的对齐

设M是X和Y的任意比对，如果(m,n)!∈M，则X的第m个位置或Y的第n个位置在M中没有匹配

在最优比对M中，至少以下之一为真
(i)（m,n)∈M
(ii)X的第m个位置不匹配
(iii)Y的第n个位置不匹配

对于i≥1和j≥1，最小比对开销满足以下递归：
OPT(i,j)=min[αxiyi+OPT(i-1,j-1), δ+OPT(i-1,j),δ+OPT(i,j-1))]

Alignment(X,Y)
  数组A[0...m,0...n]
  对每个i，初始化A[i,0]=iδ
  对每个j，初始化A[0,j]=jδ
  For j=1,...,n
    For i=1,...m
      利用递归计算OPT(i,j)公式计算A[i,j]
    Endfor
  Endfor
  Return A[m,n]

图中的最短路径

前面讨论过通过Dijkstra算法解决所有边的开销都是正数的情况，对于更一般的情况，需要用到动态规划的算法。
设G=(V,E)是有向图，假设每条边(i,j)∈E具有权重c_ij。在没有负环的情况下，考虑最小开销路径。如果G没有负环，那么存在一条从s到t的简单最短路径（没有重复节点），因此最多有n-1条边。我们用OPT(i,v)表示使用最多i条边的路径的最小开销，我们最初的问题是计算OPT(n-1,s)

如果i>0，那么
OPT(i,v)=min(OPT(i-1,v),minw∈V(OPT(i-1,w)+cvw))

Shortest-Path(G,s,t)
  n=G中点的个数
  数组M[0...n-1,V]
  对于所有其他v∈V，定义M[0,t]=0且M[0,v]=∞
  For i=1,...,n-1
    For v∈V以任何顺序
      利用递归OPT(i,v)计算M[i,v]
    Endfor
  Endfor
  Return M[n-1,s]

分治算法也是常用的一种解决问题的思路，它把输入分成几个部分，递归地求解每个部分中的问题，然后将这些子问题的解组合成一个整体解。所以，分治算法通常涉及递归关系。

归并排序：把输入分成两个相同大小的部分；通过递归分别解决这两个部分的两个子问题；然后将两个结果组合成一个整体解，只用线性时间进行初始划分和最终重组。证明归并排序的方法的时间复杂度是O(nlogn)。

求解递归的一般方法：一种是展开前几层递归，并确定递归展开时会继续的模式，然后对所有层的运行时间求和；一种是从猜测一个解开始，然后替换到递归关系中，来检查是否有效。

计数逆序：考虑两个排名，如何评估两个排名的差异有多大？我们说两个索引i<j形成逆序，就是a(i)<a(j)，即两个元素顺序不同。计算逆序的个数，数字越大，两个序列差异越大。自然的想法，需要O(n²)的时间。用分治的方法，用分治算法，类似归并排序，可以优化到O(nlogn)。

Merge-and-Count(A,B)
  对每个列表维护一个只想它的Current指针，初始化向首个元素
  维护一个变量Count记录逆序的个数，初始化为0
  While 两个列表都不为空
    令ai和bj是Current指针指向的元素
    将较小的一个添加到输出列表
    If bj是较小的元素 then
      让 Count加上A中剩下元素的个数
    Endif
    将选出较小元素的列表的Current指针向前移
  Endwhile
  当一个列表为空时，将另一个列表中剩下的元素添加到输出
  Return Count和归并的列表

寻找最近点对：给定平面中n个点，找到最近的一对点。显而易见，有一个O(n²)的算法，就是逐一计算两个点之间的距离。使用分治的思想，可以优化到O(nlogn)。考虑把点集均匀地分成两个部分，分别计算最近点。合并时考虑两个点被分在两边的情况。

Closet-Pair(P)
  构造Px和Py
  (p0*,p1*)=Closet-Pair-Rect(Px,Py)

Closet-Pair-Rect(Px,Py)
  If |P| <= 3 then
    度量所有两个点之间的距离，找到最近点对
  Endif

  构造Qx,Qy,Px,Py
   (q0*,q1*)=Closet-Pair-Rect(Qx,Qy)
   (r0*,r1*)=Closet-Pair-Rect(Rx,Ry)

  δ=min(d(q0*,q1*),d(r0*,r1*))
  x*=集合Q中点最大的x坐标
  L={(x,y):x=x*}
  S=P与L中相距在a之内的点集

  构造Sy
  For 每个点s∈Sy，计算从s到Sy中接下来15个点的所有距离
    令s,s'是其中距离最小的点对
    If d(s,s')< δ then
        Return (s,s')
    Else if d(q0*,q1*) < d(r0*,r1*)
        Return (q0*,q1*)
    Else
        Return (r0*,r1*)

这里可能有个疑问，为什么只计算从s到Sy中接下来15个点的所有距离？具体可以看书上的证明。

整数乘法：用小学生列竖式的算法，时间复杂度为O(n²)。改进的算法基于更巧妙的方式，将乘积分解为部分和。

Recurisve-Multply(x,y)
  写x=xi*2n/2+x0
    y=yi*2n/2+y0
  计算 y1+x0和y1+y0
  p=Recurisve-Multply(x1+x0,y1+y0)
  x1y1=Recurisve-Multply(x1,y1)
  x0y0=Recurisve-Multply(x0,y0)
  Return x1y1*2n+(p-x1y1-x0y0)*2n/2+x0y0

卷积和快速傅里叶变换：（略）

贪心算法可以说是最容易被人想到的算法之一，它非常符合人类在面对复杂问题时的思维方式。它大概可以描述成：如果一个算法以小步骤来构建解，在每个步骤中目光短浅地选择一个决策来优化某些基础判据，那它就是贪心的。是不是能够联想到市场经济能够形成看不见的手？自然界才是真正的算法大师，或者说，自然界是高等生物用算法设计的？如果一个问题能够被贪心算法成功地解决了，通常意味着问题本身的结构存在一个有趣且有用的东西：存在一个局部决策，可以用来构建（整体）最优解。

区间调度问题

描述：有一组请求{1,2,…,n}；第i个请求对应于一个时间区间，从s(i)开始到f(i)结束。如果在一个请求的子集中，没有两个请求在时间上重叠，我没说这个子集是相容的。我们的目标是接受尽可能大的相容子集，成为最优子集。思考过程：选择最早开始的请求？选择最小时间的请求？选择最小冲突的请求？最后发现，应该首先接受最先完成的请求。证明（略）。时间复杂度O(n log n)

最小化延迟的调度

描述：我们有一个资源和一组n个请求，假设资源在时间s开始可用，请求i有一个截止时间d(i)，它需要一个长度为t(i)的连续时间区间，不同的请求分配不能重叠。求最优子集。思考过程：按照长度t(i)增加的顺序安排作业？按照增加的宽裕时间d(i)-t(i)来排序作业？最后，只按照截止时间d(i)递增的顺序对作业进行排序。证明（略）。这种不顾及作业长度的决策，居然可以提供最优解。

最优缓存的调度

考虑存储在主存中的n个数据集合U。还有一个更快的内存（即缓存），可以在任何时候保存k<n个数据项。假设缓存最初保存k个数据项。从U中提取一系列数据项D=d₁,d₂,..d_m提供给我们，在处理它们时，必须决定在缓存中保留哪k项。当需要提供数据项d_i时，如果在缓存中，就可以非常快地访问它。如果缓存已满，则逐出其他数据，为d_i腾出空间。我们希望缓存未命中的情况尽可能少。结论：当d_i需要载入缓存时，逐出最远未来需要用到的数据项。证明（略）

求解图的最短路径

给定有向图G=(V,E)，以及一个起始节点s。假设s具有到G中每个其他节点的路径。每条边e具有长度L>=0，表示经过e所需要花费的时间。对于路径P，P的长度L(P)是P中所有路径长度之和。确定从s到图中每个其他节点的最短路径。Dijkstra算法：

Dijkstra算法(G,L)
令S是要探索的节点集
    For 每个u ∈ S，保存一个距离d(u)
初始 S={s}且d(s)=0
While S ∉ V
    选择一个节点v ∉ S，使得从S到v至少有一条边，且
    d'(v) = min d(u)+L最小
    将v加入S并定义d(v)=d'(v)
EndWhile

有没有发现这个贪心算法和梯度下降多么神似！

求解最小生成树

对于有一组位置V={v₁,v₂,…v_n}，我们希望在它们之上构建一个通信网络。网络应该联通，且尽可能便宜地构建它。Kruskal算法：从没有任何边的情况下开始，并通过增加开销的书序连续插入边，从而构建一个生成树。按此顺序加入时，只要没有产生环，就插入它，如果产生环，就抛弃并继续。另外，通过Dijkstra算法思想也可以生成最小生成树，称为Prim算法。还可以运行Kruskal算法的“后向”版本，按照开销降低的顺序删除边。这三种算法都可以达到最优解，证明略。

聚类问题

假设有集合U，包含n个对象，标记为p₁,p₂,…p_n。对于每一对p_i和p_j，有一个数值距离d(p_i,p_j)，且d(p_i,p_j) > 0，并且距离是对称的。给定一个参数k，将U中的对象划分成k个组，我们说U的k聚类，表示把划分成k个非空集合C₁,C₂,…C_k。将k聚类的间隔定义为不同聚类之间任何一对点之间的最小距离。如果寻找最大可能间隔的k聚类。通过Kruskal算法生成最小生成树时，把已经联通的节点视为一个聚类，那么当到达k个聚类时，既可以停止。

哈夫曼码与数据压缩

最优前缀码：对于指定的字母表和这些字母的频率集合，我们希望产生尽可能高效的前缀码，即每个字母的平均位数达到最小的前缀码。前缀码可以用二叉树来表示，且对应于最优前缀码的二叉树是满的。哈夫曼改进了香农-法诺码，算法如下：

对于给定频率的字母表S构建前缀码
  IF S有两个字母 then
    将一个字母编码为0，另一个字母编码为1
  Else
    令y*和z*史频率最低的两个字母
    通过删除y*和z*，并用一个新字母w代替它们，其频率是fy*+fz*，构建一个新字母表S'
    递归第为S'构建前缀码，使用树T'
    定义S的前缀码如下：
      从T'开始
      取标记为w的叶节点，并在它下面加上标记为y*和z*的两个子节点
  Endif

证明哈夫曼算法的最优性（略），时间复杂度O(klogk)

这两天读了《不拘一格》，一本介绍Netflix文化的新书，因为是其CEO亲自出版，受到特别热捧。刚好，最近一个季度的季报中，Netflix现金流首次为正，专注内容本身的模式，终于赢得了阶段性胜利。当然，这里受到疫情影响，订阅用户数增长超过了预期，但是是否能够持续，有待时间来检验。

书中讲述了Netflix文化的两个基础：
第一，提高人才密度
第二，提高坦诚度
同时，在这个基础上不断减少管控

而且这三个环节，是一个不断自我循环促进的过程，人才密度高、坦诚度高，就能够减少管控，提升自由度，提升创新能力，给出行业内最高的工资，再吸收更好更多的人才进来。这个循环一旦建立起来，企业就有了强大的自我更新的能力。

当然，如果事情这么简单，Netflix也不会如此独特了。书中讲到了很多实际运营中遇到的问题，比如去掉了休假限制，但是如果老板不亲自带头休假，仍然会人员工怀疑；比如还是能遇到员工报销与工作无关的费用。特别的，书里面提到了坦诚文化，在全球各个国家遇到的文化差异，引起的挑战。极端的以东亚，尤其日本为例，当面指出别人的问题，推行起来非常困难，所以公司也做了灵活调整，提供一些其他手段，来保持文化的尽量统一。

在混沌大学的课程里也分析过Netflix，当然角度完全不同，主要是“单点突破”的模型，公司把所有精力都投入在内容本身，去掉了节目中的广告，也去掉了市场推广，坚信好的内容能带来用户，并确实一步一步走了出来。但是在国内，爱奇艺和腾讯视频，能否走到这一步，还真难说。

Netflix文化的推行与成功，是有几个前提的。一是，公司处于一个需要创新的行业，创新能力的重要性，远远大于避免犯错的能力的重要性（书中也提到了这点）。二是，独立思考能力的人才足够多，文化适合、市场成熟。三是，公司CEO自身有足够的信念，并持之以恒。

文化复制很难，但如何激发员工的创新能力、如何提升企业运作的效率，都是值得一直思考的问题。

这几天在学习隐私计算，就是在保证数据安全的情况下，能够进行分析、挖掘、甚至机器学习，主要基于现代密码学的基础算法和协议，目前形成了三个主要的解决方案：多方安全计算、联邦学习、可信计算。把网上的资料，整理成了一个PPT，供学习参考

所有内容都来自于网络公开资料，仅供学习交流，如有侵权，请联系我删除

开源数据库ClickHouse这两年在OLAP市场异军突起，以不可思议的性能优势，让人眼前一亮。到底它为什么这么快？虽然说列存储，数据压缩是主要原因，但是同样使用列存储、数据压缩的其他产品很多，比如HBase和Druid，为什么ClickHouse一枝独秀呢？好像俄罗斯出品的软件，常常会有这样的奇迹，比如nginx、Kaspersky。

书里写到几个具体原因：充分使用硬件。ClickHouse会关注CPU的缓存，会使用SSE指令集来实现向量化执行等等。算法优先。对于每一种场景、数据量都会选择最优的算法，而且持续改进，大胆尝试新算法。持续测试，持续改进。ClickHouse的研发离不开Yandex大量真实场景和数据的测试与改进。

市面上讲ClickHouse的书不多，网上的文档也不是特别丰富。这样的情况下，一本能够讲原理。特别是讲清楚MergeTree，又能讲到很多实践，从安装部署到副本与分片的书，非常难得。

ISBN 978-7-111-65490-2