方阵的最小多项式和特征多项式是线性代数中的一个基本概念,它的计算在自动化控制、稀疏线性方程组的求解等其它领域都有重要的应用。本文先叙述了对最小多项式和特征多项式的国内外的研究历史和现状,然后给出了已有的计算常数矩阵特征多项式、多项式矩阵的特征多项式和常数矩阵最小多项式的主要算法及其复杂性。最后,我们给出了一种计算多项式矩阵最小多项式或特征多项式的有效算法,它从低次项到高次项逐项确定最小多项式的系数多项式。算法利用一个随机向量和一个随机位移,对输入矩阵没有任何条件限制。我们把这一算法与已有的算法作了理论的复杂性分析,并对我们的算法和CHTB方法做了相应的数值实验,实验结果证实了这一算法的有效性。本文提出的算法具有这样的优点:既去掉了CHTB方法的限制条件,又具有比CHACM方法更低的计算复杂性。