合并排序算法的平均情形复杂性分析及其应用

在合理的“概率分布”假设下,分析了两个有序表合并排序算法的平均情形复杂性,并将此结果应用于个元素的二分排序算法中,最后对二分排序算法的平均情形复杂性进行了估计。     

群L(3,2)的GF(2)模分解

由于G＝L(3，2)≌SL(3．2)，所以L(3，2)中的元素可表示成GF(2)上的三阶矩阵．采用基本群论和矩阵的一些方法，讨论了群L(3，2)的GF(2)模分解，特别地，对于L(3，2)的GF(2)模的可分解性进行研究．考察了L(3，2)的GF(2)模可分解成不可约模的直和，若V为G的非凡模且t∈G,o(t)=2能使|V/Cv(t)|=2，则V＝V1 V0,其中V1为G自然模，V0＝Cv(G)；若V／Cv(G)为G自然模，则V＝A V0，其中A^-为G不可约模，V^-／CV^-(G)为G自然模，且|Cv^-(G)|≤2,V0≤Cv(G)．这些结论可用于Aamalgam问题的讨论，所使用的方法可以用于更为复杂的有限群的讨论．