1963年，复杂度的概念首先是由苏联数学家A.N.柯尔莫哥洛夫（Andrey Nikolaevich Kolmogorov，1903-04-25～1987-10-20）提出来的。一般认为描述一件事物的计算机语言的长度越长，此事物就越复杂。20世纪70年代，研究者在信息理论的研究中对随机序列复杂度给出了定义，认为复杂度反映了一个时间序列随其长度的增加出现新模式的速率，表现了序列接近随机的程度。20世纪80年代末期，研究者对随机序列的复杂度进行了进一步研究，提出了随机序列复杂度测度的具体算法。这套算法得到的复杂度测度被称为Kc复杂度。由于复杂度分析方法对序列的长度要求不严格，因此在信号处理领域应用较广。

计算Kc复杂度之前，首先将要处理的序列进行粗粒化，在此对随机序列进行二值化处理，就是将序列的每一个点都由一个比特位来代表，于是就可以将所研究的信号信息粗粒化形成一个序列。假设要处理的时间传输序列为，求得平均值。如果，令；如果，令；然后将这些点组成原来序列的简化序列。

复杂度理论所研究的资源中最常见的是时间复杂度和空间复杂度。①时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明此算法效率越高，则此算法越有价值。②空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。

复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂度理论作为计算理论的分支，某种程度上被认为和算法理论是一种矛盾的关系，即算法理论专注于设计有效的算法，而复杂度理论专注于理解为什么对于某类问题，不存在有效的算法。