k分搜索的时间复杂度分析

分治策略的思想是将一个规模较大的问题分解为多个形式相同的子问题来解决。搜索是指在一个排好序的数组中寻找与给定数值x相等的元素,传统的搜索算法是遍历,而二分搜索是一种基于分治策略的搜索算法。二分搜索是将数组每次分为相等的两部分,将待查元素x与数组中间的元素比较,若相等则搜索成功;否则将搜索范围缩小为原来的一半,之后以此类推,直到找到待查元素,与遍历相比,二分搜索复杂度明显降低。以二分搜索为基础,每次可以将数组分为更多部分,即k分搜索,探寻k为何值时k分搜索算法的时间复杂度最低,能够对搜索算法进一步优化。通过分析、归纳与证明,得出k分搜索的时间复杂度为O(klog_kn),由于该函数是递增的,因此二分搜索是效率最高的搜索算法,复杂度为O(log₂n);此外,当k=n时,k分搜索退化为遍历,复杂度退化为O(n)。     

Parallel block tridiagonalization of real symmetric matrices

Two parallel block tridiagonalization algorithms and implementations for dense real symmetric matrices are presented. Block tridiagonalization is a critical pre-processing step for the block tridiagonal divide-and-conquer algorithm for computing eigensystems and is useful for many algorithms desiring the efficiencies of block structure in matrices. For an “effectively” sparse matrix, which frequently results from applications with strong locality properties, a heuristic parallel algorithm is used to transform it into a block tridiagonal matrix such that the eigenvalue errors remain bounded by some prescribed accuracy tolerance. For a dense matrix without any usable structure, orthogonal transformations are used to reduce it to block tridiagonal form using mostly level 3 BLAS operations. Numerical experiments show that block tridiagonal structure obtained from this algorithm directly affects the computational complexity of the parallel block tridiagonal divide-and-conquer eigensolver. Reduction to block tridiagonal form provides significantly lower execution times, as well as memory traffic and communication cost, over the traditional reduction to tridiagonal form for eigensystem computations.     

基于混沌伪随机序列的流密码的分割攻击

研究了文献[2]提出的基于混沌伪随机序列设计的流密码算法,分析了其信息泄漏规律.利用该算法所产生的乱数序列具有前几个比特对密钥的低位比特变化不够敏感的性质,提出了能够有效降低该流密码算法密钥熵的分割攻击方法.在密钥长度为128比特时,该分割攻击方法的成功率为0.9498,平均计算复杂性至多为279.     

基于混合神经网络的车辆路径模型研究

为有效解决现代物流配送中的车辆路径问题,发挥BP神经网络在解决分类问题和Hopfield神经网络在解决组合优化问题中的优势,依据"分而治之"策略提出了基于混合神经网络的优化模型。通过BP神经网络对一个配送中心范围内的多个配送点进行区域划分,在各子区域内使用Hopfield神经网络求得最优配送路径,从而得到质量较高的解和较快的收敛速度。基于Matlab的仿真实验结果表明,与传统的爬山算法、遗传算法相比,该模型能够获得性能更好的全局最优解。     

Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

Logistic映射敏感值的有限精度研究*

针对一维混沌加密算法密钥空间小、安全性能低的问题,提出了基于混沌大整数化的完整解决方案,把密钥空间扩大到2392。详细阐述了用于大整数运算的分治叠加法设计思路与实现要点,包括混沌大整数化步骤在内的数字图像加密步骤。以256×256的彩色数字图像为例,验证了加密耗时和加密效果。通过对密钥空间、直方图、明文敏感性、密钥敏感性、信息熵等指标进行分析,表明了基于混沌大整数化的一维混沌加密算法,可以有效抵御穷举、统计和差分等攻击,为一维混沌加密算法走向应用开拓了更大的密钥空间。最后,对密钥的自身安全和超大数字图像处理方法,给出了成熟的解决思路和方案。     

Gray码的分治构造算法

Gray码在计算机编码、通信以及工业自动化等领域具有广泛的应用。寻找一种生成并存储Gray码的快速而有效的算法是非常意义的。提出一种基于分治算法的Gray码生成方法，同时对算法的时间和空间复杂性进行了分析和讨论。实验结果验证了算法的有效性。     

基于分治策略的分布式调度自动化系统 稳态监控网络拓扑分析

电网拓扑分析是电网调度自动化系统的一项基础性工作,是联通电网模型和电网分析的桥梁,为电网调度员潮流计算、防误操作等等提供必要的基础数据。随着电网建设,网架结构逐步扩大,亟需一种方法在充分利用计算机资源的基础上实现高效率的网络拓扑分析。提出了一种基于分治思想的电网网络拓扑分析算法,通过结合电网模型的特点以及成熟的图论算法予以实现。同时将面向高级应用服务和面向监控服务的拓扑功能解耦,在不影响电力潮流计算等应用功能的基础上提高调度自动化系统集成效率,最后应用该算法编写并行的分布式电网拓扑分析程序,并展望了其应用前景。     

基于分治策略的加法器测试向量生成技术

为应对数据通道测试中向量生成计算复杂度的日益增长,针对加法器进行研究,提出了一种基于分治策略的加法器测试向量生成技术。首先将被测加法器电路分解为并发模块和顺序模块,分别生成对应这些模块故障全覆盖的测试向量子集,再将他们的输入信号映射为被测加法器电路的基本输入,经去除冗余向量后得到完整的测试向量集。给出的实验结果表明了该技术能有效地降低加法器测试向量生成的计算量,特别对于大规模加法器电路的测试生成,其效果更佳。     

分治策略在确定主导谐波和间谐波中的应用

提出一种基于分治策略的确定主导谐波和主导间谐波的算法。该算法借鉴了快速排序的思想,在分析间谐波特性的基础上,对各个谐波或间谐波分量进行排序,得到线性序列,并利用元素选择的方法确定要分析的主导谐波或间谐波分量。实验结果表明,该算法能准确、有效地确定主导谐波和间谐波。