算法的时间复杂度和空间复杂度-总结（通用5篇）
篇1：算法的时间复杂度和空间复杂度-总结
算法的时间复杂度和空间复杂度-总结
通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
一、事后统计的方法
这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。
二、事前分析估算的方法
因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。
在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
(1).算法采用的策略、方法；(2).编译产生的代码质量；(3).问题的输入规模；(4).机器执行指令的速度。
一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。
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))为算法的渐进时间复杂度，简称时间复杂度。另外，上面公式中用到的 Landau符号其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。
T(n)= Ο(f(n))表示存在一个常数C，使得在当n趋于正无穷时总有 T(n)≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T(n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n2+n +1)= O(3n2+n+3)= O(7n2 + n)= O(n2)，一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
从图中可见，我们应该尽可能选用多项式阶O(n)的算法，而不希望用指数阶的算法。常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。
（3）求解算法的时间复杂度的具体步骤是：
k
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
[java] view plaincopy 1.for(i=1;i<=n;i++)2.x++;3.for(i=1;i<=n;i++)4.for(j=1;j<=n;j++)5.x++;
第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。
一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问4294967297是不是质数？如果要直接入手的话，那么要把小于4294967297的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题。
（4）在计算算法时间复杂度时有以下几个简单的程序分析法则:
(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下“求和法则” 求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m)+ g(n))(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下“乘法法则” 乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
另外还有以下2个运算法则:(1)若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2)O(Cf(n))= O(f(n)),其中C是一个正常数
（5）下面分别对几个常见的时间复杂度进行示例说明：(1)、O(1)
Temp=i;i=j;j=temp;以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
(2)、O(n2)
2.1.交换i和j的内容
[java] view plaincopy 1.sum=0；（一次）2.for(i=1;i<=n;i++)（n+1次）3.for(j=1;j<=n;j++)（n2次）4.sum++；（n2次）
解：因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)； 2.2.[java] view plaincopy 1.for(i=1;i 该程序的时间复杂度T(n)=O(n2).一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加 1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 (3)、O(n) [java] view plaincopy 1.a=0;2.b=1;① 3.for(i=1;i<=n;i++)② 4.{ 5.s=a+b; ③ 6.b=a; ④ 7.a=s; ⑤ 8.} 解： 语句1的频度：2, 语句2的频度： n, 语句3的频度： n-1, 语句4的频度：n-1, 语句5的频度：n-1, T(n)=2+n+3(n-1)=4n-1=O(n).(4)、O(log2n) [java] view plaincopy 1.i=1;① 2.while(i<=n)3.i=i*2;② 解： 语句1的频度是1, 设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n 取最大值f(n)=log2n, T(n)=O(log2n)(5)、O(n3) [java] view plaincopy 1.for(i=0;i 一个经验规则：其中c是一个常量，如果一个算法的复杂度为c、log2n、n、n*log2n ,那么这个算法时间效率比较高，如果是2n ,3n ,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。 算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。 2、算法的空间复杂度 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。 如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。 Check_coin(a[8])//实现查找8枚硬币中的假币位置，并且判断假币比真币重还是轻 //输入一个整数a[8] //输出假币在数组的位置i，并且输出Leigh or Heavy 如果两个硬币进行比较，H保留较重硬币的下标，L保留较轻下标 拿较重硬币与真币进行比较： 如果比真币重，则返回这个硬币下标，并且返回Heavy;否则返回另一个硬币下标，并且返回Light; #include int i,sum=0; for(i=from;i<=to;i++) sum+=a[i]; return sum;} int check_coin(int a[],int from,int to){ int i,H,L; i=(to+1)%8; if(a[from]>a[to]) { H=from; L=to; } else { H=to; L=from; } if(a[H]>a[i]) { flag=1; return H; } else { flag=-1; return L; } } main(){ int a[8]; int i,p; for(i=0;i<8;i++) { printf(“a[%d]=”,i); scanf(“%d”,&a[i]); } if(sum_coin(a,0,2)==sum_coin(a,3,5)) p=check_coin(a,6,7); else { if(sum_coin(a,0,2)>sum_coin(a,3,5)) { if((a[0]+a[4])>(a[3]+a[1])) p=check_coin(a,0,3);else { if((a[0]+a[4])==(a[3]+a[1])) p=check_coin(a,2,5); else p=check_coin(a,1,4); } } else { if((a[0]+a[4])>(a[3]+a[1])) p=check_coin(a,1,4); else { if((a[0]+a[4])==(a[3]+a[1])) p=check_coin(a,2,5); else p=check_coin(a,0,3);} } } if(flag==1) printf(“the false coin is Heavy.n”); else printf(“the false coin is Light.n”); printf(“the false coin is %d.n”,p); 排序是一个按着指定的顺序排列一个给定对象集合中诸元素的过程, 排序为以后寻找一个排序的集合的元素提供了极大的方便, 在许多方面特别是数据处理领域, 排序几乎成为一项最基本的重要活动。排序无疑是示范多种多样算法的一个理想课题, 算法所要占用计算机资源的多少是分析算法好坏的主要指标, 而这些资源中运行时间 (时间消耗) 和所需存储空间 (空间占用量) 是两个主要方面, 即时间复杂度和空间复杂度。因为目前从计算机的发展来讲, 存储器容量越来越大、越来越便宜, 所以我们考虑更多的是时间复杂度。虽然现在计算机的运行速度越来越快, 但是算法的优劣与否对程序执行的效率影响还是很大的。因此, 很有必要对排序算法的时间复杂度进行细致的研究。 2 选择排序算法时间复杂度分析 选择排序的基本思想是:每一趟从待排序的记录中选出关键字最小的记录, 顺序放在已排好序的子文件的最后, 直到全部记录排序完毕。常用的选择排序方法有:直接选择排序和堆排序。 2.1 直接选择排序 这是最简单的整序算法之一, 发现最小元素并放入第一个位置, 然后找出次小元素放在第二个位置, 这样一直找下去, 直至整个数组整队好。算法如下: 这个方法适宜于小型文件。外循环i共执行n-1次;内循环j共执行n-i次, 所以共做比较次数为: undefined 该算法时间复杂度T (n) =O (n2) 。 2.2 堆排序 堆排序是一种树形选择排序, 是对直接选择排序的有效改进。堆的定义如下:具有n个元素的序列al, a2, …, an, 当且仅当该序列满足如下性质 (简称为堆性质) : ai≥a2i且ai≥a2i+1或 (2) ai≤a2i且ai≤a2i+1 (1≤i≤n/2) 前者称为大根堆, 后者称为小根堆, 在这里只讨论满足前者条件的堆。由堆的定义可以看出, 堆顶元素 (即第一个元素) 必为最大项, 完全二叉树可以很直观地表示堆的结构。堆顶为根, 其它为左子树、右子树, 树的每个节点都大于或等于其儿子节点。 堆排序的基本思想是:初始时把要排序的数的序列看作是一棵顺序存储的二叉树, 调整它们的存储顺序, 使之成为一个堆。这时堆的根节点a (1) 最大, 然后将根节点与堆的最后一个节点a (n) 交换, 再对前面n-1个数a (1) , a (2) , …, a (n-1) 重新调整使之成为堆, 然后交换a (1) 和a (n-1) 。依此类推……, 直至重建堆的元素只剩a (1) , 此时a (1) , a (2) , …, a (n) 便是从小到大排列了, 即得到有n个节点的有序序列。 从算法描述来看, 堆排序需要两个过程, 一是建立堆, 二是堆顶与堆的最后一个元素交换位置。所以堆排序由两个函数组成, 一是建堆函数, 二是反复调用建堆函数来重建堆以便实现排序的函数。算法如下: 由于初始构建堆所需的比较次数较多, 因此它并不适合待排序序列个数较少的情况。堆排序算法运行时间主要是消耗在初始构建堆, 以及在重建堆时的反复筛选上。 在初始建堆的过程中, 因为是从二叉树最下层最右边的非叶子节点开始构建, 将它与其儿子进行比较和相应的互换, 对于每个非叶子节点来说, 其实最多能进行两次比较和互换操作, 因此整个初始建堆的时间复杂度为O (n) 。 在正式堆排序时, 由于有n个节点的堆, 其对应二叉树的高度为log2n, 所以第i次取堆顶记录重建堆需要用O (log2i) 的时间, 并且需要取n-1次堆顶记录, 因此重建堆的时间复杂度为O (nlog2n) 。 所以总体来说, 堆排序的时间复杂度T (n) =O (nlog2n) 。由于堆排序对原始记录的排序状态并不敏感, 因此它无论是最好、最坏和平均时间复杂度均为O (nlog2n) 。 3 交换排序算法时间复杂度分析 交换排序的基本思想是:两两比较待排序记录的关键字, 发现两个记录的次序相反时即进行交换, 直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 3.1 冒泡排序 这种整序的基本思想是, 在整序过程中, 每次仅进行相邻两元素的比较, 它不像选择整序那样一个较小元素一下子就放在左边, 而是较大元素每次向右移动一步, 缓缓运动到右边, 活像气泡在水底运动一样, 大的下沉, 小的上浮。算法如下: 外循环共执行n-1次, 每次外循环时, 内循环分别执行n-1次、n-2次……2次、1次, 它们的和为n (n-1) /2, 所以该算法时间复杂度T (n) =O (n2) 。 算法中的flag是交换标志变量, 若在某一趟排序中未发现气泡位置的交换, 则可在此趟排序后终止。若文件的初始状态是正序的, 一趟扫描即可完成排序, 此时只比较了n-1次, 因此冒泡排序算法最好情况的时间复杂度为O (n) 。 3.2 快速排序 快速整序的基本思想是分而治之, 把序列分割成二部分然后独立地对这两个部分进行整序。实际的分割点依赖于序列的具体情况, 通常选择序列范围内最左边元素作为主元分割点。快速排序通过一趟分划扫描, 就能确保把主元放到应有的位置a[j], 并以主元为轴心将下标在[left, right]范围内的序列分成左右两个子序列。左侧子序列下标范围是[left, j-1], 其所有元素都小于等于主元;右侧子序列下标范围是[j+1, right], 其所有元素都大于等于主元。然后又用同样的方法处理它左右两边的数, 直到将它们排成有序序列。算法如下: 快速排序的时间性能取决于快速排序递归的深度, 可以用递归树来描述递归算法的执行情况。如果排序n个元素, 其递归树的深度就为log2n, 即仅需递归log2n次。 如果每次分划操作后, 左、右两个子序列的长度基本相同, 则快速排序的效率最高。第一次分划操作时, 比较次数为n-1, 所需时间为O (n) 或者cn。然后将序列平分两半, 那么各自还需要T (n/2) 的时间。不断地划分下去, 于是有以下不等式推断。 T (n) ≤2T (n/2) +cn, T (1) =0 T (n) ≤2 (2T (n/4) +cn/2) +cn=4T (n/4) +2cn T (n) ≤4 (2T (n/8) +cn/4) +2cn=8T (n/8) +3cn …… T (n) ≤nT (1) + (log2n) ×cn=O (nlog2n) 在最好的情况下, 快速排序算法的时间复杂度为O (nlog2n) 。 如果每次划分操作所产生的两个子序列, 其中一个子序列只比上一次划分少一个元素, 另一个为空序列, 则快速排序的效率最低, 这种情况发生在原始序列正向有序或反向有序时。此时需要进行n-1次递归调用, 且第i次划分需要经过n-i次比较才能找到第i个主元位置, 因此比较次数为 (n-1) + (n-2) +…+2+1=n (n-1) /2。 在最坏的情况下, 每次划分只能减少一个元素, 快速排序将不幸退化为冒泡排序, 其算法的时间复杂度为O (n2) 。 平均情况下, 不是将元素分为两个大小相等的子序列, 而是将元素分为由i-1和n-i个元素组成的两个子序列。随机地选取第i个元素为分割点 (1≤i≤n) 的概率为1/n, 分别调用quicksort (1, i-1) 和quicksort (i+1, n) 的平均时间为T (i-1) 和T (n-i) , 分割n个元素为两部分需要时间cn, 遂得: undefined 当i从1变化到n, 将出现两个T (0) 、T (1) 、…、T (n-1) , 故进一步得: undefined 又T (0) =T (1) =b (b为常数) , 由数学归纳法可证明, 其数量级为O (nlog2n) 。 该算法的平均时间复杂度T (n) =O (nlog2n) 。 4 插入排序算法时间复杂度分析 插入排序的基本思想是:每次将一个待排序的记录, 按其关键字大小插入到前面已经排好序的子文件中的适当位置, 直到全部记录插入完成为止。常用插入排序方法有直接插入排序和希尔排序。 4.1 直接插入排序 这正是人们通常打扑克时整理手上牌的方法:每次拿到一张牌, 将它插入适当位置, 使它们保持大小排序。也就是说将考虑的元素插入适当位置后, 将比其大的元素右移一个位置。算法如下: 外循环i执行时从2到变化到n, 内循环j每次执行i-1次, 所以总的比较次数为: undefined 该算法时间复杂度T (n) =O (n2) 。 当待排记录处于正序的情况时, 每次从无序表中取出第一个元素, 把它插入到有序表的合适位置, 使有序表仍然有序, 只进行了n-1次比较且没有移动数组元素就完成了整个排序过程, 所以该算法最好情况的时间复杂度为O (n) 。 4.2 希尔排序 希尔排序的本质是缩小增量排序, 是对直接插入排序算法的改进。它将待排记录序列以一定的增量间隔h分割成多个子序列, 对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h, 对于每一个步长h下的各个子序列进行同样方法的排序, 直到步长为1时, 整个要排序的数被分成一组, 再进行一次整体排序。 希尔排序的核心是以某个增量h为步长跳跃分组进行插入排序, 其关键是如何选取分组的步长序列才能使得希尔排序方法的时间效率最高, 经验表明在取下述序列:……121, 40, 13, 4, 1为最好, 这个序列由递推关系hn=3hn-1+1确定。算法如下: 在希尔排序过程中, 不管记录序列多么庞大, 关键字多么混乱, 在先前较大的分组步长h下每个子序列的规模都不大, 用直接插入排序效率都较高。尽管在随后的步长h递减分组中子序列越来越大, 但由于整个序列的有序性也越来越明显, 则排序效率依然较高。 希尔算法的时间复杂度受增量序列的影响明显大于其它因素, 选取恰当的增量序列能明显提高排序的时间效率。以上通过试验结果得到的经验序列, 也并不一定是唯一的最佳增量序列, 至今尚不清楚取什么样的h序列才是最佳的。因为希尔算法的时间复杂度是所取步长序列的函数, 到目前为止该函数在数学上仍无确定的解, 因此希尔排序的时间复杂度至今不甚明了, 这应当是一个值得进一步研究的课题。其时间复杂度T (n) 有两个猜测:一个是O (nlog22n) , 另一个是n1.25。 5结束语 不同的算法在不同的情况下运行效率有很大的差异, 若文件初始状态基本上是正序, 则应选用直接插人、冒泡或随机的快速排序为宜。若数据大小分布是随机的, 则可分为两种情况:当n不大, 如n≤50时可采用直接插入或直接选择排序:前者用于记录规模相对偏小的状态, 因为直接选择排序移动的记录个数少于直接插人排序, 所以后者用于记录规模相对偏大的状态;当n较大时, 则应采用时间复杂度为O (nlog2n) 的快速排序或堆排序, 后者不会出现前者排序时可能出现的最坏情况, 当待排序的关键字是随机分布时, 前者的平均时间最短, 快速排序是目前基于比较的内部排序中被认为是最好的方法。 从以上分析和研究中可以得到如下结论:直接选择排序算法的时间复杂度, 在最好情况、平均情况和最坏情况下均为O (n2) ;堆排序算法的时间复杂度, 在最好情况、平均情况和最坏情况下均为O (nlog2n) ;冒泡排序算法的时间复杂度在最好情况下为O (n) , 在平均情况和最坏情况下均为O (n2) ;快速排序算法的时间复杂度在最好情况、平均情况下均为O (nlog2n) , 在最坏情况下为O (n2) ;直接插入排序算法的时间复杂度在最好情况下为O (n) , 在平均情况和最坏情况下均为O (n2) ;希尔排序算法的时间复杂度, 还有待于进行更深入的研究和进一步的证明。 参考文献 [1]陈慧南.算法设计与分析[M].北京:电子工业出版社, 2009. [2]王云鹏.线性时间选择算法时间复杂度深入研究[J].电脑编程技巧与维护, 2009 (14) . 关键词低密度奇偶校验码；分层修正最小和译码算法；惰性调度 低密度奇偶校验（Low-density Parity-check）码[1] 是可以实际应用，性能接近Shannon极限的纠错编码，因而得到广泛关注，对于现在的无线通信有着至关重要的作用。在LDPC码译码时，由于校验节点与变量节点之间有大量的信息传送，因此降低LDPC码的译码复杂度与译码器的功率消耗，关键在于减少信息传送的运算量。 Gallager在提出LDPC码的同时给出了一种基于概率域的迭代译码算法，这就是目前被普遍采用的置信传播算法（Belief Propagation），又称为和积算法（Sum-Product Algorithm简称SPA）。借助于和积算法，LDPC码可获得最优的译码性能，但校验节点计算中的双曲余切函数 为算法的硬件带来了很大的困难。分层最小和译码算法用min（x）最小值函数代替了复杂的 函数，大大降低了译码算法的复杂度，而译码性能与和积算法非常接近。 一、分层最小和译码算法 分层译码的思想是将LDPC码的校验矩阵按水平方向分层，每一层可看作独立的码，各层的交集构成完整的码， 假设校验矩阵可分为M层，其中每一层的最大列重为1，译码时顺序处理每一层，所有M层参加完一次译码后完成一次迭代。记变量节点i的初始对数似然率（LLR）信息为 ；第n次迭代中，变量节点i传向第l层中检验节点j的LLR信息为 ；第l层的校验节点j传向变量节点i的LLR信息为 ；变量节点i的后验概率信息为 ；与校验节点j相连的变量节点集合记为N（j）。 分层置信传播译码时，首先进行初始化： = 随后对校验矩阵进行逐层译码，在每一层中变量节点i传向校验节点j的信息为： =- =- 校验节点j返回至变量节点i输出信息为: = × 其中 ， 表示与校验节点j相连的除去i节点外的变量节点的集合。同时更新变量节点的后验信息 = + 由于函数 的实现较为复杂，因此可将置信传播中 的简化为求最小值运算，得到最小和译码。同样，可将分层译码运用于最小和算法。此时校验节点的处理有所不同； = × 将和积算法简化为最小和运算后，将带来性能损失。因为最小和算法是高信噪比情况下对校验节点处理的简化，在一般情况下，其校验节点的输出信息都要大于最优的和积算法，因此，可以对最小和算法中校验节点输出的信息乘以乘性因子α（α<1）进行补偿； 在分层译码的最小和算法中引入乘性因子，得到分层修正最小和译码算法。 二、惰性调度在分层修正最小和译码算法的应用 在以上LDPC码译码算法中，经少量迭代次数，变量节点信息就可以稳定的传送，当变量节点信息的后验概率达到很高时（>98%）就可以使变量节点在接下来的迭代中处于睡眠状态，不再对传入和传出的信息进行更新，因此会减少很多的运算量，并且也不会影响到译码的结果。减少复杂度的分层修正最小和算法（R-L-MSA）如下： 当变量节点后验信息 超过设定值 ，将进行以下操作： （1）变量节点后验概率信息 不会被更新，(6)式不会执行，无法影响到硬判决的结果。 （2）校验节点传向变量节点的信息 无法更新，（5）式跳过。 （3）变量节点传向校验节点的信息 无法更新，（3）式不能跳过，因为（4）式中的S的计算需要参量 。而当变量节点后验概率信息 能够稳定的传递时，不会影响到（3）式也不会直接跳到（7）式，这样简化了对校验信息的读取。 我们应设定合适的 值，如果设置的太低，则会出现“地板效应”。这时的处理方法是，译码器定时的唤醒睡眠节点来更新信息，这一定时可以设置为 次迭代。exe（）（ 小于其设定值 ，当前迭代次数到达 时）决定是否要唤醒变量节点，被唤醒后的节点，根据更新的信息来决定其工作状态。 三、LDPC码译码器的结构 基于改进算法，我们设计了译码器结构。 图1 译码器结构 Fig.1 Decoder architecture 比特信息单元（Get Bit Information unit）执行算法中的（3）式和（7）式； 串处理单元（Serial processing unit）执行（4）式； 信道信息单元（Get channel information unit）执行（5）和（6）式； 这样可以看出，我们增添译码器的部分为变量节点向量寄存器（variable node vector register ），其向量值与码长相等，用来监控变量节点是否处于睡眠状态。判断单元判定 值是否超过了设定值 ，并将结果反馈到变量节点向量寄存器。判定的结果又决定了惰性调度的控制器是否要执行检验节点与变量节点的信息传送。 当 值超过了设定值 时，检验信息将不会在其存储器中被读取；在信道信息单元没有任何运算，更新校验信息和变量节点后验信息不再需要，当然也就没有必要写入其相应的存储器中，此时变量节点处于睡眠状态。 四、仿真 我们对提出的算法进行了计算机仿真。仿真时取码长1024，码率R=1/2，采用BPSK调制和加性高斯白噪声信道，最大迭代次数为30.仿真结果如图2所示，在信噪比为0.8dB-1.3dB时减少分层的最小和译码算法（R-L-MSA，取 =10， =5）的误码率要优于和积算法（Sum-Product Algorithm），而最小和算法的译码性能则较差。 图2 MSA，SPA和R-L-MSA（ =10， =5）算法的性能比较 SNR (dB)MSA (K Ops)SPA (K Ops)运算量减少百分比（%）R-L-MSA (K Ops)运算量减少百分比（%） 17109786742465.446502899.33 3986478303718.797501331.51 5593144786323.923812144.21 73370240753-17.302296546.75 9131464265-55.97825259.30 图3 R-L-MSA（ =10， =5）与SMA、SPA相比减少的运算量百分比 Fig3、Operation of R-L-MSA（ =10， =5）reduction comparison with SMA、SPA 五、结论 为了进一步降低分层最小和译码算法的复杂度，在此篇论文中，我们提出了减少复杂度的分层最小和译码算法，当变量节点的后验信息概率较高时，变量节点处于睡眠状态，达到了目的。仿真结果表明我们改进的算法使变量节点运算量减少接近60%，减少了译码器的功率消耗，并保持了译码的良好性能。 参考文献 [1] R G Gallager. Low -Density -Parity –Check Codes.IER Transactions on Information Theory,1962:21-28. [2] A Anastasopoulos.A Comparison between the sum –product and the min-sum iterative detection algorithms based on desity evolution[C]//.Global Telecommunications Conference(Volume2).San Antonio ,Tx,2001:25-29. [3] F Zarkeshvari,A H Banihahemi.On imp lamentation of min-sum algorithm for decoding Low-desity parity-check (LDPC)codes[C]//.Global Telecommunications Conference (Volume 2).Taipei,2002:17-21. [4] SL Howard,V C Gaudet,C Schlegel. Soft-BitDecoding of Regular Low-Density Parity-Check Codes.IEEE Transactions on Circuits and systemsⅡ,2005,P(99) . [5] Hocevar D. A reduced complexity decoder architecture via layered decoding of LDPC codes [C]//IEEE Workshop on signal processing systems,sips:Design and Implementation .Austin,Texas,USA:IEEE,2004;107-112. [6] Fossorier M,Mihaijevic’M,Imai H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation.IEEE Tranactions on communications,1999,47(5):673-680. [7] Chen JH,Fossorier M Density evolution for two im2 proved BP2 based decoding algorithms of LDPC codes.IEEE Communications Letters,2002,6(5):208-210. 关键词 沪深300股票指数；复杂度；kolmogorov熵；样本熵；模糊熵 中图分类号 F830 文献标识码 A AbstractThis paper studied the high frequency data of the CSI 300 index， and examined the efficiency of complexity measures such as Kolmogorov entropy， sample entropy and fuzzy entropy in high frequency environment. By using the effective measurement， it compared the changing process and range of the complexity both before and after the subprime crisis. The results show that， compared with the Kolmogorov entropy based on the compatible method and sample entropy， fuzzy entropy is more suitable for measuring the CSI300 index's complexity， which has the lower sensitivity to the similar tolerance and the better continuity of measure value. The CSI 300 index's complexity is rising during the sample interval. However， the complexity during the crisis is far more less than the two other stages， and the complexity after the crisis is higher than that before the crisis. Compared with the developed markets and even some emerging markets， the CSI 300 index's complexity is much lower. Key wordsthe CSI 300 index； complexity； Kolmogorov entropy； sample entropy； fuzzy entropy 1问题提出与相关文献回顾 根据混沌理论，复杂度被定义为非线性动力系统或序列的复杂性程度[1].其大动态范围、短平稳性和小数据量的特征被认为是最适于分析非线性系统的动力学特征参数，也是非线性动力系统研究的重要方面[2].沪深300股票指数是联系我国股票现货市场与股指期货市场之间的重要桥梁，金融机构往往需在日内动态调整资产头寸并关注风险管理，因此，沪深300股票指数高频数据的复杂性程度对于风险管理和交易策略实施均具有重要意义.在我国市场环境下，有效地复杂度测算方法是什么？与成熟市场和周边的新兴市场相比，我国沪深300股票指数的复杂度如何？围绕次贷危机的影响，不同时间阶段其复杂度的变化幅度与变化过程如何？既有研究尚未对上述系列重要问题做出较为全面地解答，同时学术界和实务界对采用何种方法来进行复杂度测算亦尚未达成共识. 早期文献表明，关于混沌序列复杂度的研究始于20世纪60年代.西方学者提出了各种相关测度指标与方法，但成果主要集中于工程计算领域.随着金融市场非线性动力学行为与混沌效应的存在性逐渐得到实证，关于股价波动复杂度的测算研究成为热点，但方法局限于围绕分形维数的测算，研究结论也在多重分形错觉方面存在较大争议[3，4]. 近年来，学者们运用不同类型的熵模型展开了复杂度测算研究，主要包括柯尔莫哥洛夫熵（kolmogorov）、近似熵（ApEn）、样本熵（SampEn）和模糊熵（FuzzyEn）算法.kolmogorov（1965）将复杂度界定为能够产生某一（0，1）序列所需的最短程序的比特数，并形成Kolmogorov熵算法.Lempel和Ziv（1976）给出了其在计算机中实现的具体算法.对此，肖辉，吴冲锋，吴文峰，等（2002）将之应用于中国股票市场检测，计算了沪市综合指数与深市成份指数的复杂度[5].尽管该算法有着严格的数学理论基础和依据，但因需将给定时间序列转换成符号序列，使得转换方法成为该算法在股价波动复杂度测算应用时的关键.然而，均值法、极值法和遗传密码法三种主要转换方法均未考虑序列整体性质，亦不能区分弱混沌与周期序列，以及强混沌与随机序列（Abuasad， ect.， 2012）[6].综合法（He，Xu，2000）为解决上述问题，按不同时间序列分别应用均值法和极值法，但受限于需事先明确知道时间序列性质（赵波等，2014）.对此，王福来和达庆利（2007）提出了基于兼容法的Kolmogorov熵算法并应用于上证综合指数日收盘价序列复杂度测算[7]，为Kolmogorov熵算法缺陷问题的解决提供了新视角. 由于近似熵算法（Pincus，1995）采用Heaviside函数进行相似性量度，敏感于阀值和相空间维数，从而参数选取会使其计算精度带有经验性（蔡觉平，李赞，宋文涛，2003）.样本熵算法通过不计算自身匹配的统计量，对其形成了改进，但在无模板匹配的情况下可能出现ln0的无意义结果（贺少波，尹林子，阿地力·多力坤，2012）.对此，学术界相继提出了多种改进方法.肖方红，阎桂荣和韩宇航（2004）将混沌伪随机序列看成符号序列，提出符号熵算法.虽然该算法不涉及参数的选取，计算比近似熵算法更为简单，但符号熵算法需预先知道符号空间，且只针对伪随机序列，应用范围局限性较大.Chen（2011）在对样本熵（SampEn）进行改进基础上提出模糊熵（FuzzyEn）算法，并基于TDERCS系统成功检验了其有效性（贺少波，尹林子，阿地力·多力坤，2012）[8].模拟显示，基于模糊熵的复杂度测算方法可能在对参数依赖的敏感性方面更低，测度值的连续性更好，从而获得更高的测度效率（李鹏，等，2013）[9]. 文章的创新之处在于：1）不仅较为全面的对比了各种基于熵算法的复杂度模型测算效率，而且进行了小样本修正，以期为沪深300股票指数复杂度测算提供可靠的实证依据与分析结论.2）围绕次贷危机的影响分阶段研究和比较了危机前、中、后期序列复杂度的变化过程与变化幅度，并与发达市场乃至周边新兴市场股指期货标的指数的复杂度相较，得到我国沪深300股票指数复杂度的演化规律与独特性质. 2代表性熵算法、有限样本修正 与测算效率评价标准 通过对相关研究成果的梳理可知，对既有测算效率形成一定改进后的代表性熵算法主要集中为基于兼容法的Kolmogorov熵、样本熵和模糊熵.重构相空间维数m、相似容限度r和序列长度N是测算过程中的共同关键变量.如模糊熵： 当时间长度足够长时，MFDFA方法计算得到的h（q）是较准确的，但在实际应用中，序列长度很难满足要求，此时有限样本会使h（q）的计算产生偏误，进而也会使关联维数以及熵计算中的相空间维数m产生偏误，因此需要对MFDFA中的有限样本效应进行修正，以提升测算和评价结果的准确性.修正方法基本思路为：利用Liu（2007）和吴栩等（2014）对马尔科夫转换多重分形模型（MSM）的解析，构造能够尽可能反映原始股指序列多重分形特征的模拟序列，该模拟序列的长度应该足够的长，从而可以消除MFDFA计算中的有限样本效应. 在测算复杂度的过程中，对模型效率的评价标准主要集中于算法本身的稳定性和结果对模型参数的依赖程度，即，算法鲁棒性，对相空间维数、相似容限度和时间序列长度的敏感性和依赖性，以及测度结果的连续性[11].由于是对我国沪深300股票指数运动的复杂度进行测算，而复杂度的标准值尚未知，不同于在某些性质既定和已知正确结果的复杂系统下对研究方法的评价，因此，通过算法鲁棒性来评价模型效率的路径尚不能行通.在熵算法模型中股指序列长度N既定，相空间维数m通过计算获得，测度值对参数的敏感性和依赖性，以及结果的连续性主要与相似容限度r密切相关[12].因此可以认为，当在相似容限度的经验取值范围内，某一算法未出现错误度量值，其测度结果趋于稳定且图像相对平滑，则该算法对相似容限度的敏感性和依赖性较低，测度效率相对较高. 3数据说明与采样频率筛选 以2005年5月9日至2013年12月31日沪深300股票指数1分钟、5分钟、10分钟、15分钟和60分钟高频数据 选择了相关研究中主要出现的若干种高频频率作为筛选对象.作为基础研究样本.数据来源为Reset数据库.虽然我国沪深300股票指数于2005年4月8日上市，但考虑到上市之初，市场各方对该指数存在熟悉过程[13]，为准确起见，在数据选取时剔除掉了2005年4月的交易数据. 直接采用股票指数而未如传统证券市场定量分析采用收益率数据 在有关证券市场的定量分析中通常使用收益率样本而不是指数本身，主要是考虑到价格序列的相关性违反以高斯假设和正态分布为基础的线性分析框架原则.，主要缘于文章的复杂性研究视角，避免收益率变量可能对系统非线性相依结构所形成的破坏. 沪深300股票指数1分钟、5分钟、10分钟、15分钟和60分钟高频数据的描述性统计结果如表1所示， 其中IF1、IF5、IF10、IF15和IF60依次对应不同采样频率.统计结果显示，各种不同采样频率的高频数据都表现出有偏和尖峰厚尾的统计特征，且明显超出了正态分布假定的范围（JarqueBera统计量显著） .因此，可以认为各序列明显具有非线性特质. 鉴于不同采样频率可能会带来不同检验结果，在进行复杂度测算之前需要进行有效采样频率甄别.由既有熵测算方法可知，相空间维数是各熵算法中的关键变量.较窄的多重分形度置信区间对应较精确的维数.因此，遵从多重分形度置信区间计算方法，以对多重分形度置信区间宽度的比较筛选有效高频采样频率，比较结果如表2所示. 根据表2结果可知：各采样频率下经有限样本效应修正后的多重分形度均仍接近于1，我国沪深300股票指数运行具有多重分形特征；置信区间宽度随采样间隔的增加而变化，其中当间隔为5分钟时宽度最窄.从而，沪深300股票指数5分钟高频数据为进行复杂度测算的有效采样频率数据. 为方便与发达市场和周边新兴市场的股指期货标的指数复杂度的对比，文章还选择了标准普尔500指数、日经225指数和韩国指数2005年5月9日至2013年12月31日的5分钟高频数据，作为第四部分对比分析中的研究数据. 4沪深300股票指数高频数据复杂度的 熵测算实证结果与分析 由于涉及了三种熵算法模型，且模型中至少涉及了三种关键参数，为了清晰起见，此处不逐一报告参数的估计结果，而是直接展示对应熵算法下的复杂度结果，及其随关键参数值改变而变化的过程，并进一步进行模型测算效率评价. 4.1关键参数值的确定 由熵算法步骤可知，重构相空间维数m、相似容限度r和序列长度N是测算过程中的关键变量，需要对其进行准确数值确定. 在上述三变量中，时间序列长度N由给定样本区间决定.经筛选，研究中的基础样本为2005年5月9日至2013年12月31日的沪深300股票指数5分钟高频数据，时间序列总长度N= 689 330. 相似容限度r属于熵算法模型中的阀值变量，其值过小会增加结果对噪声的敏感性，过大则会导致信息丢失，根据Chen（2009）的模拟建议，r的取值一般可在[0.3，0.35]中选取. 对相空间维数m的选取，相关研究通常使用经验值.由于尽管较大的m能细致重构系统的动态演化过程，但亦会陡增运算量，m取值通常为2、3、4、5和6.为了更为准确衡量指数复杂度，可以基于所提出的有限样本修正方法计算获取合理m值.依第二部分中的修正算法得到测算后的适宜m值为3 鉴于篇幅有限，小样本修正的计算步骤在此不作列示，仅给出最后结果.有兴趣的读者可与作者联系.. 4.2全样本区间内的测算结果与模型测算效 率比较 基于兼容法的Kolmogorov熵算法的计算结果显示，全样本区间内我国沪深300股票指数的复杂度为1.057 1，超出了该算法复杂度值的（0，1）值域.考虑到全样本区间可能因数据存在结构突变而导致虚假统计结果，运用计算程序每次取其连续的1 000个数据在有限样本效应修正下进行分析，然后取其均值作为序列平均复杂度.结果显示，平均复杂度为1.049 9，依然超出了Kolmogorov熵算法复杂度的值域范围.说明基于兼容法的Kolmogorov熵算法并不适用于对我国沪深300股票指数复杂度的测算 其原因可能缘于该算法在序列复杂度接近于1时分辨率不高.但整体结果与分段后均值结果均超出了值域范围，已经说明该方法失效.文章并不旨在分析该方法失效的原因，因此不再对此进行深入说明.. 图1（a）、（b）依次显示的是样本熵和模糊熵两种算法对复杂度的估计结果.虽然相似容限度r的经验值取范围为[0.3，0.35]，但为了更便于分析研究方法的效率，在编写程序过程中令r从0到0.5以0.001等间距变化 以0.001的间距变化趋近连续变化.，并对应计算复杂度值，以观察结果的连续性及其对参数变化的敏感程度.从图1（a）（b）中可以看出，样本熵和模糊熵算法均测出了复杂度计算结果，且计算结果整体比较接近.复杂度值均随r的增大而减小，当r取值为[0.3，0.35]时，其所估计的沪深300股票指数复杂度值相对其他区间内的复杂度值平稳，数值在0.55到0.43之间（如图1（a）和（b）中的虚线区域部分）. 相似容限度（a）样本熵算法下沪深300股票指数复杂度的估计结果 相似容限度（b）模糊熵算法下沪深300股票指数复杂度的估计结果 在测度结果的连续性与对参数的敏感性方面，样本熵测度结果在r的整个取值范围[0，0.5]内出现多个跳跃点，且在[0.3，0.35]范围内的跳跃点明显多于模糊熵（如图1（a）中的虚线区域部分），说明模糊熵算法相对于样本熵算法对相似容忍度的敏感性更低，测度值的连续性更高.有限样本效应修正后，当r取[0.3，0.35]时，模糊熵算法下的复杂度均值为0.494 9. 4.3不同时段沪深300股票指数复杂度结果 比较 为进一步刻画我国沪深300股票指数复杂度，在对测算方法评估后，本部分基于模糊熵算法，对全样本区间内不同时段复杂度进行测算比较. 从2005年5月9日至2013年12月31日的全样本区间可划分为2005年5月9日到2007年9月30日的指数高速攀升阶段，2007年10月8日到2009年3月31日的危机阶段和2009年4月1日到2013年12月31日的后危机阶段（其涵盖了我国股指期货从2010年4月16日推出并运行至今的阶段）三个阶段.各阶段复杂度值如表3所示. 虽然各阶段时间序列长度不尽相同，但由于模糊熵算法优于样本熵和Kolmogorov熵复杂度算法，且当N值在10 000左右时，模糊熵算法本身具有对时间序列长度较高的一致性，经有限样本效应修正后此种一致性效果会进一步增强.因此，分阶段后时间序列长度的不一致并不会对分阶段研究的计算结果形成显著影响. 如表3所示，各阶段复杂度测算结果表明，在危机前中国股市的集中上涨时段，指数复杂度为0.462 3；指数受危机冲击而大幅下挫阶段的复杂度为0.427 1；后危机时代的指数复杂度为0.510 2.其说明我国沪深300股票指数复杂度以后危机时代阶段为最高，受危机冲击阶段为最低. 美国次贷危机前我国股票指数运行表现为整体性快速上涨，受危机影响阶段表现为指数整体大幅下挫，两阶段股指运行均呈现出较强规律性，其市场投资者行为较单一，符合规律性序列复杂度较低的复杂度数值性质.而指数下跌阶段复杂度低于上涨阶段复杂度，则提示出沪深300股票指数在下跌阶段趋势性更强.这一点与股指波动非对称性（陈浪南，黄杰鲲，2002；陆贤伟，董大勇，纪春霞，2009；顾锋娟，金德环2013）特征一致.指数在后危机时代复杂度得到提升，说明危机冲击及相关股市政策改革后，我国沪深300股票指数运行的单一趋势性有所转化，投资者行为多样性得到补充；同时，在后危机阶段我国股指期货正式推出运行，也说明股指期货的推出对打破股票市场运行单一趋势性与修正波动时间一定程度上发挥了作用. 4.4不同市场股指期货标的指数复杂度比较 为了便于与发达市场和周边新兴市场的股指期货标的指数复杂度进行对比，此处选择了标准普尔500指数、日经225指数和韩国指数2005年5月9日至2013年12月31日的5分钟高频数据作为对比样本.基于模糊熵算法，全样本区间内发达市场和周边新兴市场的股指期货标的指数复杂度测算结果如表4所示；2009年4月1日到2013年12月1日的后危机阶段的复杂度测算结果如表5所示. 通过对比各个不同股票市场的复杂度，不难发现，无论是全样本区间还是后危机阶段，发达股票市场的复杂度均大于我国股票市场的复杂度；其中，我国沪深300股票指数复杂度以与标准普尔500指数复杂度差距为最大，与韩国指数复杂度最为接近；而在后危机阶段，我国沪深300股票指数运行的复杂度较其他国家股指期货标的指数复杂度的差距均有所减小.说明，我国沪深300股票指数相对于代表性发达市场和周边新兴市场股指期货标的指数的可预测性更明显，潜在的市场投机性更大；而随着我国股票市场相关监督和运作体系的完善以及股指期货的推出，市场逐渐成熟，可预测性有所降低，投机性正在逐渐被削减. 5结论 文章对我国沪深300股票指数高频数据复杂度测算方法及复杂度特征进行了研究.通过运用3种新兴主流熵算法以及有限样本效应的修正，研究了3种算法对沪深300股票指数复杂度测算适用性以及不同时段和不同市场对比下我国沪深300股票指数复杂度变化和差异. 主要实证结果显示： 第一，在日内高频数据环境下，与基于兼容法的kolmogorov熵和样本熵算法相比，模糊熵算法是一种更适用于研究我国沪深300股票指数的有效的复杂度测算方法.其对相似容忍度参数的敏感性更低，测度结果的连续性更好.第二，随着时间的推移，我国沪深300股票指数序列复杂度整体呈上升趋势.但危机中阶段指数序列的复杂度远小于危机前后两阶段的复杂度，后危机阶段复杂度高于危机前阶段复杂度；相较于危机中阶段，后危机阶段复杂度的上升速度较快.第三，相较于发达市场甚至周边新兴市场股指期货标的指数，我国沪深300股票指数的复杂度呈现偏低结果. 针对实证研究的政策建议如下： 第一，鉴于虽然在后危机阶段（包括股指期货的推出）我国沪深300股票指数复杂度得到了快速上升，但与其他市场股指期货标的指数运行情况相比仍然偏低.而比较公认的观点是，偏低的复杂度对应市场投资者行为多样性不足，市场运行的不可预测性较弱.因此，为了稳定沪深300股票指数运动，减少较多一致性投机行为，增加机构投资者参与数量，提高预测难度. 第二，由于多种类型机构投资者可以丰富不同环境下期货与现货指数市场的投资行为，并对市场稳定起到积极作用从而提升市场复杂度（魏宇，赖晓东，余江，2013），目前我国还需转变机构投资者投资策略，避免一致性追涨杀跌，引导机构投资者端正投资理念，发挥其在股票市场中的稳定作用. 第三，由于实证结果表明，在日内高频环境下，模糊熵算法具有更好的适用性.因此，在监测沪深300股票指数复杂度时可采用该方法进行测算，以便获得更为准确的结果.基于兼容法的kolmogorov熵算法虽然较基础性kolmogorov熵算法形成了改进，但分析结果也表明了其对我国沪深300股票指数的不适用性.虽然在研究过程中还可对其形成进一步改进，但其计算过程相较于模糊熵算法的繁琐性也是明显的.因此，如果考虑到运算成本和使用难度等问题，模糊熵算法是监测我国沪深300股票指数复杂度的不错选择. 参考文献 [1]张林，李荣钧，刘小龙. 基于小波领袖多重分形分析法的股市有效性及风险检测[J]. 中国管理科学，2014，22（6）：17-26. [2]陈小军，李赞，白宝明，等. 一种确定混沌伪随机序列复杂度的模糊关系熵测度[J]. 物理学报，2011，60（6）：064215. [3]魏宇，赖晓东，余江.沪深300股指期货日内避险模型及效率研究[J].管理科学学报，2013，16（3）：29-40. [4]周炜星.上证指数高频数据的多重分形错觉[J].管理科学学报，2010，13（3） ：81-86. [5]肖辉，吴冲锋，吴文峰，等.复杂性度量法在股票市场中的应用[J].系统工程理论与实践，2002，11（3）：190-197. [6]A ABUASAD，M I ALSMADI. Evaluating the correlation between software defect and design couping metrics[C]//2012 International Conference on Computer Information and Telecommunication Systems（CITS）. Washington DC： IEEE Computer，2012：1-5. [7]王福来，达庆利.Co复杂度的改进及其在证券市场中的应用[J].数学的实践与认识，2007，37（8）：20-25. [8]贺少波，尹林子，阿地力·多力坤.模糊熵算法在混沌序列复杂度分析中的应用[J].物理学报，2012，61（13）：130507. [9]李鹏，刘澄玉，李丽萍，等.多尺度多变量模糊熵分析[J] .物理学报，2013，62（12）：120512. [10]J KANTELHARDT，S ZSCHIEGNER. Multifractal detrended fluctuation analysis of nonstationary time series[J]. Physica A，2004（2）：49-83. [11]I SOROKIN. Comparing files using structural entropy[J]. Journal in Comuter Virology， 2011， 7（4）：259-265. [12]Ruipeng LIU， T D MATTEO， L THOMAS. True and apparent scaling： The proximity of the Markovswitching multifractal model to longrange dependence[J]. Physica A： Statistical Mechanics and its Applications，2007，383（1）：35-42.篇2：算法的时间复杂度和空间复杂度-总结
篇3：排序算法时间复杂度研究
篇4：算法的时间复杂度和空间复杂度-总结
篇5：算法的时间复杂度和空间复杂度-总结
