随着计算方法的发展,几乎所有的学科都走向定量化和精确化,从而产生了诸如计算数学、计算物理、计算生物学等一系列的计算科学。计算科学的发展促进了学科之间的交叉和渗透,从而促进了各个学科的发展,但各个学科的复杂性和非线性特征也日益明显。复杂性科学与复杂系统研究逐渐成为热点。演化分析是探索复杂科学的基本手段。王能超教授的一系列工作表明,二分技术可以刻画自然演化的基本特征和机制,是演化分析的基本模式,是研制高效算法的强大平台。本论文目的在于探讨二分技术在探索复杂性科学及高效算法设计中的应用,考察了计算科学领域三类重要的复杂系统:Walsh函数系统,分形几何以及生物信息学。研究了Walsh函数系统理论,以Hadamard变换为例子,设计了二维Walsh变换的一个快速算法,其性能明显优于行列算法。设计了空间填充曲线的三种算法:几何算法,代数算法及几何代数混合算法。基于演化思想,几何算法通过基本元素的确定、变换和组合三个步骤完成了Peano空间填充曲线的生成。代数算法将曲线数字化,采用矩阵复制方法,完成了Hilbert曲线的绘制,并进一步应用于基于Hilbert序的编码解码,使得该编码解码算法的时间复杂度小于相关算法且有更宽广的适用范围。混合算法考虑了Hilbert曲线的几何特征,利用辅助代数矩阵完成了曲线的绘制,该算法比经典的L系统算法提高了将近1倍的速度。基于代数算法的思想,对Hilbert曲线向三角域作了推广。通过对含有概率的迭代函数系统(IFS)的仿射变换系数进行改造,将IFS的动态迭代问题静态化,使之成为典型一阶线性递推问题。以混沌游戏为例子,利用二分技术对这类递推问题进行了并行算法设计,分析了这类算法的时间和空间复杂性以及适用范围。设计了创建Neighbor-Joining进化树的一个快速算法,其性能优于同类算法。研究了Gusfield提出的星型比对模型的串行算法,进行了时空上的改进,基于Cluster结构的并行机提出了一种并行算法,实验表明对于大规模的多序列比对,算法能达到较高加速比。