| 关于整数向量卷积的一个算法的时间复杂度 |
| |
| 引用本文： | 张振祥.关于整数向量卷积的一个算法的时间复杂度[J].计算数学,1993,15(1):93-94. |
| |
| 作者姓名： | 张振祥 |
| |
| 作者单位： | 安徽师范大学 中国科大研究生院信息安全国家重点实验室 |
| |
| 摘 要： | 众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出1]的错误原因,再根据算法分析理论得出1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。
|
| 关 键 词： | 整数向量卷积 算法 时间复杂度 |
ON THE COMPLEXITY OF AN ALGORITHM FOR INTEGER VECTOR CONVELUTIONS |
| |
| Institution: | Zhang Zhen-xiang State Key Laboratory of Information Security, and Anhui Normal University |
| |
| Abstract: | The complexity of the conventional algorithm for cyclic convolution of twon-vectors with integer entries is O(n~2). Wu and Jiang 1] give an "optimal"algorithm with "complexity" O(n). In this paper we conclude that the complexityof their algorithm is not lower than O(n~2 log_2 n), so it is worse than the conve-ntional algorithm. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《计算数学》浏览原始摘要信息 |
| 点击此处可从《计算数学》下载免费的PDF全文 |
|
