寻找我的弱点
范文一：遗传算法时间优化
t -104. 4-() 2. 34?t ≥104. 4?1-e 94. 55, F (t ) =? t <104. 4?0,="">
j
B
i R
i
i R
j B
k i i k i k -1i -1(t -t ) M [F (t -t ) -F (t -t ∑B R B R B R )]Q
T =(t -t ) M [F (t ) -F (t )]+
T =min ∑T i
i =1P
k =j +1
i j i
t t 其中Q =12，P =18，R , B , M 是非负变量，以下是三个变量的取值：
注：初始种群为30代，交叉概率0.7，变异概率0.2，遗传代数取800
（1）要求源程序能够画出T 与遗传代数的关系图；
（2）源程序能够给出j 分别取1，2， 3，…，12时的T 的值（共12个）。
范文二：基于模拟退火—遗传算法的非线性密钥序列生成器线性复杂度研究
【 摘 要 】 计算线性等价是研究非线性密钥序列生成器线性复杂度的有效方法。本文先介绍了计算线性等价的模拟退火法，然后使用遗传算法对该算法进行改进，最后使用一组密钥序列生成器对改进后的算法进行性能评估，并将改进后的算法和原算法进行了比较。结果表明改进后的算法能比原算法更有效的找到非线性密钥序列生成器的线性等价。
【 关键词 】 线性等价；模拟退火；遗传算法；序列密码
【 中图分类号 】 TP309 【 文献标识码 】 A
1 引言
在序列密码理论中线性复杂度是非常重要的安全性尺度，许多学者在这方面都做了研究。Garcia和Fuster-Sabater2000致力于分析非线密钥序列生成器的线性复杂度 ；Wasan等学者指出，寻找线性等价是一种确定非线性密钥序列生成器线性复杂度的有效方法，并提出了基于模拟退火法（Simulated Annealing，简写为SA）计算线性等价的方法。
模拟退火法具有较强的局部搜索能力，然而全局搜索能力偏弱。遗传算法（Genetic Algorithm，简写为GA）的全局搜索能力较强。模拟退火—遗传算法已经被广泛的应用在各个领域，取得了令人满意的结果。因此，我们基于Wasan等学者的方法，使用遗传算法对其进行改进，提高了算法的效率。这篇论文包含了对算法的描述，对算法效率和性能的研究，另外还有改进后算法和原算法的对比。
2 计算线性等价遗传算法描述
为了更好地阐述非线性密钥序列生成器线性等价问题，首先对其进行遗传算法描述。遗传算法有五个关键步骤：确定候选解的表示方法；随机生成初始种群；评价每个个体（染色体）的适应度；从种群出选出一些个体作为父代，使用交叉和变异操作来产生子代；重复评价适应度并产生子代直到生成满意的结果。
2.1 表示方法
在遗传算法中，用到了不同长度的染色体。使用二进制序列来代表染色体，每条染色体表示一个线性反馈移位寄存器（Linear Feedback Shift Register下记为LFSR）的反馈函数。这些染色体就是给出的密钥序列长度的候选线性等价，假设长度lengthkey为2L。最短染色体的长度是2bit，最长染色体的长度是2Lbit。
2.2 适应度函数
适应度函数用来评估每条染色体ch。适应度函数通过等式①给出。
Fitness（ch）=（lengthkey-d）+（lengthkey/3）× ①
在（1）式中lengthkey-d用来判定生成密钥序列的准确性， lengthkey/3判定最短的LFSR是哪个从而得出最佳结果。1/（1+L（ch）是补充系数，其中L（ch）是染色体ch的长度。
2.3 适应度计算算法
每条染色体的适应度ch通过下述算法得到。
Step1： L（ch）=Length（ch） //令L（ch）成为将要被评估的染色体ch的长度
Step2： w=LFSR（a0……aL-1） //令w为LFSR的初态，即最初的长度为L（ch）的密钥序列
Step3： g（ch）=ch（w） //用ch和w生成二进制的序列g（ch）
Step4： d=Hamming（key，g（ch））//计算密钥序列和g（ch）的汉明距离
Step5： Fitness（ch）=（lengthkey-d）+（lengthkey/3）（1/（1+L（ch））） //通过等式（1）计算这条染色体的适应度
2.4 遗传参数
采用1点交叉和5%概率变异的基因操作来更新种群。种群大小n依赖于已知的密钥序列的长度lengthkey。因此随着密钥序列长度lengthkey的增加，种群大小n应当同时增加。设种群大小计算公式为n=lengthkey20。
父代个体通过基因的交叉和变异操作产生子代个体。
2.5 停止条件
遗传算法的运行在繁殖一定代产生之后停止。问题的解为最后一代种群中适应度最高的染色体。问题的解应该有适应度lengthkey+L，该染色体代表了非线性密钥序列生成器的线性等价。
3 计算非线性密钥序列生成器线性等价算法
影响遗传算法性能的关键因素就是淘汰策略，即是从当前的种群中如何选择最优的个体作为下一代种群的个体。这部分研究内容，我们提出了SA-GA1和SA-GA2两个算法来计算非线性密钥序列生成器的线性等价。遗传算法中的染色体表示方案、基因参数和适应度函数都应用到了SA-GA1、SA-GA2算法中。
SA-GA1算法先随机生成初始种群并计算种群整体适应度，然后通过交叉和变异操作该种群繁殖新一代种群同时计算新种群的整体适应度。如果新种群整体适应度较大就淘汰老种群；否则按照模拟退火法以一定概率淘汰老种群。直到降温到预定温度。图1是SA-GA1算法的流程图。
SA-GA2算法先随机生成初始种群并从中随机选择两条染色体（父代）计算适应度，然后通过交叉和变异操作父代繁殖子代同时计算子代的适应度。如果子代适应度较大就淘汰父代；否则按照模拟退火法以一定概率淘汰父代。直到降温到预定温度。图2是SA-GA2算法的流程图。
从算法的流程图中可以看到2个算法的不同：SA-GA1算法是以种群整体启发的，SA-GA2算法是以染色体个体启发的。
4 仿真实验及结果分析
为了验证本文提出的改进算法的有效性，使用C语言编程实现了SA-GA1和SA-GA2 算法，并进行了多次仿真实验。为了说明改进算法的有效性，本实验所使用的11组不同长度密钥序列的线性等价与参考文献[3]中的相同。模拟退火初始温度设置为300，停止温度为100，每繁殖一代降温为当前温度0.99。输入的密钥序列长度为2L，L的长度从3到13，通过LFSR的特征多项式来生成这些密钥序列，其中特征多项式如表1所示。 实验结果成功的概率P如表2所示，P是通过对每个密钥序列执行算法多次，其中成功地找到了问题的解，即最后一代种群中的最好染色体是想要得到的LFSR的次数而计算得到的。
图3可以更直观地看出原始算法和改进后算法成功的概率。
通过表2和图3的对比可以看出模拟退火法和遗传算法的集成提高了算法的性能，改进算法SA-GA1和SA-GA2成功找到线性等价的概率大于原始算法。仿真实验表明，在计算非线性密钥序列生成器线性等价的问题中，模拟退火—遗传算法的性能明显优于模拟退火法。
5 结束语
我们在Wasan原有算法的基础上，提出了计算非线密钥序列生成器线性等价的新方法。首先对其进行了遗传算法描述；然后结合模拟退火法和遗传算法，提出了两种改进算法，并详细阐述改进算法的步骤与两种改进算法的区别；最后通过仿真实验验证了改进算法的性能优于原始算法，是解决非线性密钥序列生成器线性复杂度问题的有效方法。
参考文献
[1] Massey， J， L. Shift register synthesis and BCH decoding[J]. IEEE Transation on infomation theory， 1969， 1（15）： 122-127.
[2] Garcia-Villalba，L.J.；Fuster-Sabater A. On the linear complexity of the sequences generated by nonlinear filterings [J]. Information Processing Letters， 2000， 76（1）： 67-73.
[3] Wasan Shaker Awad. Finding Linear Equivalence of Keystream Generators[J]. Information Technonlgy Journal， 2008， 7（3）： 541-544.
[4] 罗晨，李渊，刘勇等. 基于模拟退火遗传算法的多agent系统任务分配[J].计算机应用研究，2012，29（6）： 2114-2116.
[5] 王庆荣，袁占亭，张秋余.基于改进遗传—模拟退火算法的公交排班优化研究[J].计算机应用研究， 2012， 29（7）： 2461-2463.
[6] Jun Song， Fan Yang， Maocai， Wang. Cryptanalysis of Transposition Cipher Using Simulated Annealing Genetic Algorithm[J]. Lecture Notes in Computer Science， 2008， 5370（1）： 795-802.
[7] 马永杰，云文霞.遗传算法研究进展[J].计算机应用研究， 2012， 29（4）： 1201-1210.
作者简介：
张斌（1987-），男，硕士研究生，主要研究方向：信息安全。
缪祥华，副教授，博士后。
唐鸣，硕士研究生。
赵之洛，硕士研究生。
范文三：算法复杂度——时间复杂度和空间复杂度
1.时间复杂度
(1)时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=,(f(n)),称,(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时
22间频度不相同时，时间复杂度有可能相同，如 T(n)=n+3n+4与T(n)=4n+2n+1它们的频度
2不同，但时间复杂度相同，都为O(n)。按数量级递增排列，常见的时间复杂度有:常数阶
222O(1),对数阶O(logn),线性阶O(n), 线性对数阶O(nlogn),平方阶O(n)，立方阶
3O(n),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。 (3)渐进时间复杂度评价算法时间性能 主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。
23【例3(7】有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n，T2(n)=5n。
(1)当输入量n,20时，有T1(n),T2(n)，后者花费的时间较少。
3 (2)随着问题规模n的增大，两个算法的时间开销之比5n/100n2=n/20亦随着增大。
23即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n)和O(n)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
33【例3(8】算法MatrixMultiply的时间复杂度一般为T(n)=O(n)，f(n)=n是该算法中语
句(5)的频度。下面再举例说明如何求算法的时间复杂度。
【例3(9】交换i和j的内容。
Temp=i; i=j; j=temp; 以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作 T(n)=O(1)。 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 【例3(10】变量计数之一。
(1) x=0;y=0;
(2) for(k-1;k<=n;k++)>
(3) x++;
(4) for(i=1;i<=n;i++)>
(5) for(j=1;j<=n;j++)>
(6) y++;
一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、
2，终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是 (6)，其频度为f(n)=n
2所以该程序段的时间复杂度为T(n)=O(n)。 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
【例3(11】变量计数之二。
(1) x=1;
(2) for(i=1;i<=n;i++)>
(3) for(j=1;j<=i;j++)>
(4) for(k=1;k<=j;k++) (5)="" x++;="">
该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环
33向外层分析语句(5)的执行次数: 则该程序段的时间复杂度为T(n)=O(n/6+低次项)=O(n)。(4)算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 【例3(12】在数值A[0..n-1]中查找给定值K的算法大致如下: (1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;
此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关: ?若A中没有与K相等的元素，则语句(3)的频度f(n)=n; ?若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。(5)最坏时间复杂度和平均时间复杂度 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
【例3(19】查找算法
【例1?8】在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。
常见的时间复杂度按数量级递增排列依次为:常数0(1)、对数阶0(log2n)、线形阶0(n)、
23)立方阶0(n)、…、k次方阶0(nk)、指数阶0(2n)。显线形对数阶0(nlog2n)、平方阶0(n
然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。
2、类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着 n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。
分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元;若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表不开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1);
2n);当一个算法当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间;若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间;反之，当=i自求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
算法的时间复杂度和空间复杂度合称为算法的复杂度。
范文四：时间复杂度
时间复杂度:如果一个问题的规模是 n , 解这一问题的某一算法所需要的时间为 T(n), 它是 n 的某一函数, T(n)称为这一算法的“时间复杂度”。 渐近时间复杂度:当输入量 n 逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂度”。
当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算法分析时,往往对两者不予区分,经常是将渐近时 间复杂度 T(n)=O(f(n))简称为时间复杂度,其中的 f(n)一般是算法中频度最大的语句频度。
此外,算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以 保证算法的运行时间不会比它更长。
常见的时间复杂度,按数量级递增排列依次为:常数阶 O(1)、对数阶 O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n^2)、立方 阶 O(n^3)、 k 次方阶 O(n^k)、指数阶 O(2^n)。
下面我们通过例子加以说明,让大家碰到问题时知道如何去解决。
1、设三个函数 f,g,h 分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn
请判断下列关系是否成立:
(1) f(n)=O(g(n))
(2) g(n)=O(f(n))
(3) h(n)=O(n^1.5)
(4) h(n)=O(nlgn)
这 里我们复习一下渐近时间复杂度的表示法 T(n)=O(f(n)),这里的
◆ (1)成立。题中由于两个函数的最高次项都是 n^3,因此当 n→∞时,两个函数的比值是一个常数,所以这个关系式是成立的。
◆ (2)成立。与上同理。
◆ (3)成立。与上同理。
◆ (4)不成立。由于当 n→∞时 n^1.5比 nlgn 递增的快,所以 h(n)与 nlgn 的比值不是常数,故不成立。
2、设 n 为正整数,利用大
(1) i=1; k=0
while(i<>
{ k=k+10*i;i++;
}
解答:T(n)=n-1, T(n)=O(n), 这个函数是按线性阶递增的。
(2) x=n; // n>1
while (x>=(y+1)*(y+1))
y++;
解答:T(n)=n1/2 , T(n)=O(n1/2), 最坏的情况是 y=0,那么循环的次数是 n1/2次,这是一个按平方根阶递增的函数。
(3) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
解答: T(n)=O(1), 这个程序看起来有点吓人,总共循环运行了 1000次,但是我们看到 n 没有 ? 没。这段程序的运行是和 n 无关的,就算它 再循环一万年,我们也不管他,只是一个常数阶的函数。
3. 常数阶 O(1)
Temp=i;i=j;j=temp;
以上三条单个语句的频度均为 1,该程序段的执行时间是一个与问题规模 n 无关的常数。算法的时间复杂度为常数阶,记作 T(n)=O(1)。如果 算法的执行时 间不随着问题规模 n 的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度 是 O(1)。
4. 平方阶 O(n^2)
(1) 交换 i 和 j 的内容
sum=0; (一次)
for(i=1;i<=n;i++) (n="" 次="">
for(j=1;j<=n;j++) (n^2次="">
sum++; (n^2次 )
解:T(n)=2n^2+n+1 =O(n^2)
(2)
for (i=1;i<>
{
y=y+1; ①
for (j=0;j<>
x++; ②
}
解:语句 1的频度是 n-1
语句 2的频度是 (n-1)*(2n+1)=2n^2-n-1 f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度 T(n)=O(n^2). 5. 线性阶 O(n)
(1)
a=0;
b=1; ①
for (i=2;i<=n;i++)>
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解:语句 1的频度:2,
语句 2的频度: n,
语句 3的频度: n-1,
语句 4的频度:n-1,
语句 5的频度:n-1, T(n)=2+n+3(n-1)=4n-1=O(n).
6. 线性对数阶 O(log2n )
(1)
i=1; ①
while (i<>
i=i*2; ②
解:语句 1的频度是 1,
设语句 2的频度是 f(n), 则:2^f(n)<><=log2n 取最大值="" f(n)="">
T(n)=O(log2n )
O(n^3)
(2)
for(i=0;i<>
{
for(j=0;j<>
{
for(k=0;k<>
x=x+2;
}
}
解:当 i=m, j=k的时候 , 内层循环的次数为 k 当 i=m时 , j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了 0+1+...+m-1=(m-1)m/2次所以 ,i 从 0取到 n, 则循环共进行了 : 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为 O(n^3).
我们还应该区分算法的最坏情况的行为和期望行为。 如快速排序的最 坏情况运行时间是 O(n^2), 但期望时间是 O(nlogn)。 通过每次都仔细 地 选择基准值,我们有可能把平方情况 (即 O(n^2)情况 ) 的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间 运行。
下面是一些常用的记法:
(1)访问数组中的元素是常数时间操作,或说 O(1)操作。
(2)一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。
(3)用 strcmp 比较两个具有 n 个字符的串需要 O(n)时间 。
(4)常规的矩阵乘算法是 O(n^3),因为算出每个元素都需要将 n 对 元素相乘并加到一起,所有元素的个数是 n^2。
(5)指数时间算法通常来源于需要求出所有可能结果。例如, n 个元 素的集合共有 2n 个子集 , 所以要求出所有子集的算法将是 O(2n)的 。指 数算法一般说来是太复杂了,除非 n 的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如 著名 的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况, 通常应该用寻找近似最佳结果的算法替代 之。
(6)有如下复杂度关系经验规则
c < log2n="">< n="">< n="" *="" log2n="">< n^2="">< n^3="">< 2^n="">< 3^n=""><>
其中 c 是一个常量,如果一个算法的复杂度为 c 、 log2N 、 n 、 n*log2N ,那么这个算法时间效率比较高 ,如果是 2^n , 3^n ,n!,那么 稍微大一些的 n 就会令这个算法不能动了,居于中间的几个则差强人意。
范文五：有关时间复杂度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。 但我们不可能也没有必要对每个算法都上机测试, 只需知道哪个算法花费的时间多, 哪个算 法花费的时间少就可以了。 并且一个算法花费的时间与算法中语句的执行次数成 正比例 , 哪 个算法中语句执行次数多, 它花费时间就多。 一个算法中的语句执行次数称为语句频度或时 间频度。 记为 T(n)。 一般情况下, 算法的基本操作重复执行的次数是问题规模 n 的某一个函 数 f (n ) ,因此,算法的 时间复杂度 记做:T (n ) =O(f (n ) ) 。随着问题规模 n 的增大,算 法执行的时间的增长率和 f (n )的增长率成正比,所以 f (n )越小,算法的 时间复杂度 越 低,算法的效率越高。在计算 时间复杂度 的时候, 先找出算法的基本操作, 然后根据相应的 各语句确定它的执行次数,再找出 T (n )的同 数量级 (它的同 数量级 有以下:1, Log 2n , n , nLog 2n , n 的平方, n 的三次方, 2的 n 次方, n ! ) ,找出后, f (n ) =该 数量级 。 按数量级递增排列,常见的时间复杂度有:常数阶 O(1),对数阶 O(log2n), 线性阶 O(n),线性对数阶 O(nlog2n), 平方阶 O(n^2),立方阶 O(n^3),..., k 次方阶 O(n^k), 指数阶 O(2^n) 。 随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
举几个具体的例子:
1、 for i:=1 to 100 do
for j:=1 to 100 do s[i,j]:=0; 执行次数 100*100次,时间复杂度 O(1)
2、 for i:=1 to n do
for j:=1 to 200 do s[i,j]:=0; 执行次数 n*200次,时间复杂度 O(n)
3、 for i:=1 to n do
for j:=1 to n div 2 do s[i,j]:=0; 执行次数 n*n/2次,时间复杂度 O(n^2)
4、 for i:=1 to n do
for j:=1 to n-1 do
for k:=1 to n-2 do s[i,j,k]:=0; 执行次数 n*(n-1)*(n-2)次,时间复杂度 O(n^3) 5、 for i:=1 to n do
begin
for j:=1 to n do s[i,j,0]:=0;
for j:=1 to n do for k:=1 to n do s[i,j,k]:=1;
end; 执行次数 n*(n+n*n)次,时间复杂度 O(n^3)
