Introduction
无论是中位数查找问题，k分位数查找问题，或是排序问题，它们都是偏序产生问题的特例。这里不在赘述偏序的定义，我们让(P=(<_P,Y))是(Y={y_1,y_2,...,y_n})上的一个偏序。从一个给定的输入集合(X={x_1,x_2,...,x_n})中产生P是指：找到一个((1,2,...,n))的自同构(delta)，使得(y_i <_P y_j)可以推出(x_{delta(i)}<_P x_{delta(j)}).实际上，从直观上看的话，相当于找到一种把X中的数填到偏序P所对应的n个位置上，当然，要满足偏序的要求。
对任何一个偏序产生算法，我们都可以将其与一颗称为"决策树"的二叉树T对应起来。决策树的每个结点是一个比较(x_i:x_j)，比较的结果导致了两个分叉，叶节点是算法的输出，它是上一段中描述的自同构。比较次数即从根节点到叶的长度。算法的最坏代价(COST)即最坏比较次数，当然是决策树的最大高度。至于平均比较次数，就是把输入看成等可能的情况所得到的平均比较次数。
如果自同构(delta)将({1,2,...,n})填充到偏序P中，并且满足偏序条件（即(y_i<_P y_j)可推出(y_{delta(i)}<_P y_{delta(j)})），则称作与P相容。记(Delta (P))是所有与P相容的自同构组成的集合，记(mu (P)=|Delta (P)|)。定义C(P)为最坏比较次数，(ar{C}(P))是平均比较次数。
Schonhage的研究指出(C(P)geq log_2 (n!/mu(P))),随后Aigner指出，此下界可以渐进地达到,在(C(P)=O(log_2 (n!/mu (P)) +n))的意义下。在本文中，A.C.Yao证明了
Thm1.(ar{C}(P) = Omega (n-eta(P)+log_2(n!/mu(P))))
Thm2.(C(P) = O(n-eta(P)+log_2 (n!/mu(P))))
从而得出
Thm3.(C(P) = Theta(ar{C}(P)))
即偏序产生问题的平均意义复杂度和最坏复杂度是同阶的。其中(eta(P))指偏序P中的连通分支数量，由于偏序实际上可以用一个无圈有向图表示，这里的连通实际上就是有向图的弱连通而已。
Thm1
Thm1来自两个引理
Lem1.(ar{C}(P)geq log_2(n!/mu(P)))
Lem2.(ar{C}(P) geq n-eta (P))
Lem1考虑了到达决策树每个叶子(l)所产生的偏序(Q_l)，这些偏序(Q_l)当然是包含P的,从而(mu(Q)leq mu(P))，并且和(Q_l)相容的初始输入会输出到对应的叶子这样的话，并且所有(mu(Q_l)/n!)的和为1(因为任何输入都唯一地决定一个输出)，利用信息论的结论就可以给出(ar{C}(P))的下界。
Lem2直观上十分显然，所以不再赘述证明。
Thm2
Yao先证明了Thm4.(C(P)leq lambda (n-1+log_2 (frac{n!}{mu (P)})))，由它容易得出Thm2.
为了证明Thm4只需要给出一个满足条件的算法就可以了。
准备
称(Ain Y)是一个P的独立集，如果对于所有不同的(y,y'in A)都有y不小于y'.P的宽度是P的最大独立集的规模。P的一个k-分割是一个k元子集组((A_1,A_2,...,A_k)),各(A_k)是对集合P的一个分割，并且(A_i<_P A_{i+1})，这里的小于是指任何(A_i)的元素小于(A_{i+1})的元素。这里尤其要介绍两类特别的分割。让(B_p = (B_{p,1},B_{p,2},B_{p,3}))，(B_{p,2})是Y的一个极大独立集(Y_p)，(B_{p,1}={y| y<_P y' for some y'in Y_p}),(B_{p,3}=Y-Y_p-B_{p,1})，这是一个3-分割。记(M_p)是所有满足(|A_1|=lceil n/2
ceil,|A_2| =lfloor n/2
floor)的2-分割((A_1,A_2))组成的集合。让(D_p=(D_{p,1},D_{p,2}) in M_p)且(mu(P_1) mu(P_2))达到最大。接下来，有
Lem3. (kin {2,3}),让I是({1,2,...,n})的子集，并且(n_1,n_2,...,n_k)满足(sum_{1leq i leq k}n_i=|I|),那么存在一个高度为(c_k |I|)的决策树T，给定任何n个不同的数(X={x_1,x_2,...,x_n}),T决定了互不相交的(I_1,I_2,...,I_k)满足(a)(cup_i I_i = I),(b)(|I_i|=n_i),(c)(X_{I_i}<X_{I_2}<cdots<X_{I_k})
其中(c_2=40,c_3=80).此引理用了另外文献中的选择算法。
Procedure POPROD
算法的思路是不断递归地将偏序分解为三部分或者两部分(根据上述的“感兴趣”的两种分割，Lem3给出了分割方法)，当当前偏序的宽度大于(n/100)时，将它分成三部分，小于(n/100)时将它分成两部分。如果分成三部分，那么对于中间的独立集(B_{p,2})，我们可以将Lem3得出的(X_2)与它任意地一一对应(因为(B_{p,2})是独立的)，而对于两边的偏序，则递归继续分解，直到偏序集的大小变为1，此时将输入集唯一对应即可。（可以发现，当宽度变为1时，即偏序变为线性序时，算法实际上是一个归并排序）
经过一些繁琐但并不复杂的分析，可以知道POPROD满足Thm4，于是Thm2得到证明。