複雜度(Complexity, CPX)，指的是在給定樣本中不同DNA 序列的總長度，是一件事物的複雜性可以用描寫這事物所需的計算機語言的長度來衡量。
基本介紹
- 中文名：複雜度
- 外文名：Complexity
- 注釋：種類較多
- 分類：3種
一般定義,算法,
一般定義
還指同一杯咖啡中所並存的不同層次的特色，複雜度高，表示可以感受到的感官刺激種類較多；要注意的是這些感覺包括了餘韻，不一定限制於喝時的當下感受。
算法
複雜度（計算機複雜性理論）
空間複雜度是指計算機科學領域完成一個算法所需要占用的存儲空間，一般是輸入參數的函式。它是算法優劣的重要度量指標，一般來說，空間複雜度越小，算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有X個字（word）屬於這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。
複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種“矛”與“盾”的關係，即算法理論專注於設計有效的算法，而複雜性理論專注於理解為什麼對於某類問題，不存在有效的算法。
複雜度(Complexity, CPX) ：
複雜度的概念首先是由Kolmgorov提出來的。簡明說就是一件事物的複雜性可以用描寫這事物所用的計算機語言的長度來衡量。一般認為描述一件事物的計算機語言的長度越長，該事物就越複雜。70年代Lemple等在信息理論的研究中對隨機序列複雜性給出了定義， 認為複雜性反映了一個時間序列隨其長度的增加出現新模式的速率， 表現了序列接近隨機的程度。80年代末期Kasper 等對隨機序列Lem-Ziv意義下的複雜度進行了研究，提出了隨機序列複雜性測度的具體算法。這套算法得到的複雜性測度被稱為Kc複雜度，並且指出此算法比Lyapunov指數優越。由於複雜度分析方法對序列的長度要求不嚴格，因此在信號處理領域套用較廣。
計算Kc之前，首先將要處理的序列進行粗粒化，在此對隨機序列進行二值化處理，就是將序列的每一個點都由一個比特位來代表，於是就可以將所研究的信號信息粗粒化形成一個“0，1”序列。假設要處理的時間傳輸序列為{xi)(i=1，2，…，n)，求得平均值。如果xi≥平均值，令xi=1；如果xi<平均值，令xi=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)，這樣的結果比粗粒化複雜度更為精確。
