摘要
对于一类问题P,如果能找到一个算法（对串行计算而言）其计算复杂性为f1（u）,则称f1（n）为问题P固有复杂度的上界,若问题P的所有算法（对串行计算而言）其计算复杂性不小于f2（n）,则称f2（u）为问题P固有复杂度下界.
In this paper, we show that it requires at least [(1/4n^2)-(1/2n)] arithmetic opera-tions for inverting Toeplitz matrices. Then it immediately follows from Trench'sresult that the inherent complexity of inverting Toeplitz matrices is O(n^2). Weconsider the relation of computational complexity between inverting Toeplitz matri-ces and inverting Hankel matrices and show that the inherent complexity of invertingHankel matrices is also O(n^2), where n is the order of matrices and [x] denotesthe integer floor function of x.
出处
《应用数学学报》
CSCD
北大核心
1990年第2期216-222,共7页
Acta Mathematicae Applicatae Sinica
