关于整数向量卷积的一个算法的时间复杂度 |
| |
引用本文: | 张振祥. 关于整数向量卷积的一个算法的时间复杂度[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 |
| |
Affiliation: | 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 维普 等数据库收录! |
| 点击此处可从《计算数学》浏览原始摘要信息 |
|
点击此处可从《计算数学》下载全文 |
|