计算复杂度的分析方法

1.复杂度判定标准和基本定义

通常，对算法效率在理论上的探讨又称为算法的事先估计，可分为算法的时间复杂度分析和空间复杂度分析，其定义如下[408]：

（1）算法的时间复杂度：算法的时间复杂度是指求解该问题的所有算法中时间复杂性最小的算法时间复杂度。

在算法的设计和分析中，沿用实用性的复杂度概念，即把求解问题的关键操作（如加、减、乘、除、比较等运算）指定为基本操作，通常把算法执行基本操作的次数定义为算法的时间复杂度。

（2）算法的空间复杂度：算法的空间复杂度是指求解该问题的所有算法中空间复杂度最小的算法空间复杂度。

在实际应用中，通常把算法执行时间内所占用的存储单元定义为算法的空间复杂度。

（3）给定自然数n的两个函数F（n）与G（n），当且仅当存在一个正常数K和一个n0，使得当n≥n0时，有F（n）≤KG（n），则称函数F（n）以函数G（n）为界，记作F（n）=O（G（n）），或称F（n）是O（G（n））。此处的“O”表示数量级的概念。

在分析算法复杂度时，可以求出复杂度函数p（n），也可以用复杂度函数主要项的阶O（p（n））来表示。若算法A的时间复杂度TA（n）=O（p（n）），且p（n）为n的多项式函数，则称算法A为多项式算法，而把时间复杂度大于多项式时间的算法统成为指数时间算法。

以卫星舱布局问题为例，对遗传算法（GA）、基于Potter框架的协同进化算法（CCGA）和本书的带启发式协调机制的协同进化算法CGACS进行时间复杂度和空间复杂度分析，上述3种算法的复杂度可表示为问题规模n（待布物的数量）的函数，其中把时间复杂度记为T（n），而把空间复杂度记为S（n）。

2.算法的时间复杂度分析

算法的时间复杂度分析的目的在于说明实现相同功能的不同算法的计算效率高低[409]。因此，实际中通常采用时间复杂度的渐进表示法，说明程序执行步数的数量级，从而估算算法执行效率的高低。

设n为卫星舱布局问题的待布物数量，m1为GA的群体规模，m2为CCGA和CGACS的子群体规模，设CCGA和CGACS均包括3个子群体，为简化起见，假设每一个子群体包含待布物数量为n/3，循环次数为NG，CGACS中的局部搜索选择个体的数量为mL，局部搜索循环次数为NL，组合规则选择个体的数量为mC，组合规则循环次数为NC，旋转规则的群体规模为m1，旋转规则循环次数为NR，交叉概率为0.9，变异概率为0.01，两点交叉，则针对上述3种算法程序结构流程的描述，可逐步分析出其时间复杂度，如表4.1所示。

表4.1　GA、CCGA和CGACS的时间复杂度分析

当n足够大时，低次幂的影响可以忽略不计，则由表4.1可知，对于具有n个待布物的卫星舱布局问题，群体规模为m1的GA，则整个计算过程的时间复杂度为

TGA(n)=O(m1·NG·n2)　(4.23)

同理，对于具有n个待布物的卫星舱布局问题，子群体规模为m2的CCGA和CGACS，则整个计算过程的时间复杂度分别为(www.xing528.com)

TCCGA(n)=O(m2·NG·n2)　(4.24)

TCGACS(n)=O((m2·NG+mL·NL)n2)　(4.25)

由上述计算结果可知，当n≥m1，n≥m2，n≥NG，n≥NL，这几个条件任意一个满足时，3种算法的时间复杂度均为O（n2）。当待布物规模n一定时，从上述式中也可以看出，CGACS中的局部搜索规则在同一数量级上增加了算法的计算工作量，因此为了减少CGACS与其他算法的计算工作量差异，CGACS中的局部搜索规则中选取的局部搜索个体数量和算法循环次数不能设置过大，而本书算法采用局部搜索规则的目的与上述目的一致，仅仅是对协同进化后期较少的几个优秀个体进行短期的局部搜索，因此本文的局部搜索规则参数mL、NL一般设置较小。

3.算法的空间复杂度分析

算法在实现过程中所需要用到的数据对其空间复杂度影响很大，此处的空间是指算法在执行过程中所占用的存储单元大小。算法执行过程中所占用的存储单元主要体现在两个方面：一是问题的描述；二是算法功能实现。

对于本书的卫星舱布局问题，假设问题规模为n，则需要一个C×n阶一维矩阵描述问题本身的特征，其中C为一常数。

对于GA，假设群体规模为m1，则需要一个3×n阶一维矩阵描述最优个体特征，需要3×n×m1阶一维矩阵来描述群体特征。

对于CCGA，假设各个子群体规模为m2，包括3个子群体，各个子群体所包含的待布物规模为均为n/3，则需要3个3×（n/3）×3=3n阶一维矩阵描述各个子群体最优个体特征，需要3×3×（n/3）×m2=3×n×m2阶一维矩阵来描述群体特征。

对于CGACS，假设各个子群体规模为m2，包括3个子群体，各个子群体所包含的待布物规模为均为n/3，算法中的局部搜索选择个体的数量为mL，组合规则选择个体的数量为mC，旋转规则的群体规模为m1，则需要三个3×（n/3）×3=3n阶一维矩阵描述各个子群体最优个体特征，需要3×3×（n/3）×m2=3×n×m2阶一维矩阵来描述群体特征，需要2×n×mL阶一维矩阵来描述局部搜索个体特征，需要3×mC阶一维矩阵来描述组合个体特征，需要n×m1阶一维矩阵来描述旋转群体特征。

有上述计算结果可知，GA的空间复杂度为

SGA(n)=O(n)+O(nm1)　(4.26)

CCGA的空间复杂度为

SCCGA(n)=O(n)+O(nm2)　(4.27)

CGACS的空间复杂度为

SCGACS(n)=O(n)+O(n(m2+m1+mL))　(4.28)

上述可知，当n足够大时，在数据存上3种算法的空间复杂度均为O（n）。

可以看出，3种算法的复杂度相同，且随着待布物规模的增大，三种算法计算工作量差异会逐渐变小，同时也说明研究的CGACS更适合于求解规模较大的复杂布局问题。