关于序集碰撞数问题深度贪心算法的最优性

§1.引言称P=(X,≤)是一个序集是指,X是一个集合,“≤”是X上的一个二元关系(叫做小于等于),它满足:(1)自反性,(x≤x,x∈X),(2)传递性(x≤y,y≤z■x≤z)和(3)反对称性x≤y,y≤x,■x=y)。本文只讨论有限序集。用|X|或|P|表示序集P=(X,≤)所含有的元素个数,用x∈P或x∈X表示x是P的元素。对任一序集Q,我们也用相同的字母Q表示它的基本集。在序集P中,如果x≤y,则我们也用x≤y(P),y≥x及y≥x(P)来表示这一关系。