复杂度算法复杂度（计算机复杂性理论）计算复杂性理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源

计算复杂性理论所研究的资源中最常见的是时间复杂度（要通过多少步才能解决问题）和空间复杂度（在解决问题时需要多少内存）

其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数

时间复杂度越小，说明该算法效率越高，则该算法越有价值

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数

它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好

我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间

复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源

而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法

复杂度(Complexity, CPX)  ：复杂度的概念首先是由Kolmgorov提出来的

简明说就是一件事物的复杂性可以用描写这事物所用的计算机语言的长度来衡量

一般认为描述一件事物的计算机语言的长度越长，该事物就越复杂

70年代Lemple等在信息理论的研究中对随机序列复杂性给出了定义， 认为复杂性反映了一个时间序列随其长度的增加出现新模式的速率， 表现了序列接近随机的程度

80年代末期Kasper 等对随机序列Lem-Ziv意义下的复杂度进行了研究，提出了随机序列复杂性测度的具体算法

这套算法得到的复杂性测度被称为Kc复杂度，并且指出此算法比Lyapunov指数优越

由于复杂度分析方法对序列的长度要求不严格，因此在信号处理领域应用较广

计算Kc之前，首先将要处理的序列进行粗粒化，在此对随机序列进行二值化处理，就是将序列的每一个点都由一个比特位来代表，于是就可以将所研究的信号信息粗粒化形成一个“0，1”序列

假设要处理的时间传输序列为(i=1，2，…，n)，求得平均值

如果≥平均值，令=1；如果<平均值，令=0；然后将这些0，1点组成原来序列的简化序列

Kc的计算即找出序列x中所含的模式数，具体方法是通过一个“0，1”时间序列中的一串字符s(s1，s2，．．．，s

)后再加一个或一串字符Q，看字符Q是否属于SQv(SQv是SQ字符串中减去最后一个字符而得到的)，如果出现的字句在前面已经有过，即Q是sQ咛的一个子串，则该字符称为“复制”，认为这个过程没有新模式出现，把该字符加在串的后面，继续增长Q，再进行判断；若它没有出现过，那么对这个字符进行“插入”，“插入”时用一个“·”把前后字符分开，认为出现了一个新的模式：然后把最后一个“·”前面所有字符看成s，重新构造Q，再重复上述操作直到该序列结束并计算发现的模式数的总和

例如序列(0010)的复杂度可由下面的步骤得出：(1)第一个字符永远是插入0·；(2) S=0，Q=0，SQ=00，SQv=0，Q属于字句SQv，0·0；(3)s=0，Q=01，sQ=001，sQv=00，Q不属于字句sQv，0·01·；(4) S=001，Q=0，SQ=0010，SQv=001，Q属于字句SQv，0·01·0

于是得出该序列的模式数为3，即复杂度c(4)=3

符号序列0000…应是最简单的，0·000…，c(n)=2

另外，如010101…应是0.1.0101…，c(n)=3

如上所述，用“·”将字符串分成了段，段的数目就定义为复杂度c(n)，几乎所有的“0，1”序列的c(n)都趋向于一个定值，即：limc(n)=b(n) = n/ln(n)所以，b(n)是随机序列的渐进行为，可利用它使c(n)归一化，成为相对复杂度：C(n) = c(n)/b(n)用这种函数来表达时间序列的复杂变化，可以看出完全随机的序列的C(n)趋于1，其他规律的和周期的运动则趋于0，而不完全随机序列的c(n)介于二者之间

粗粒化的过程并不一定局限于二值化，也可以用四值化(孙红 et al.2002)或者称作细粒化的方法(陈宏伟and陈亚珠，2004)，这样的结果比粗粒化复杂度更为精确

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。