複雜度

還指同一杯咖啡中所並存的不同層次的特色，複雜度高，表示可以感受到的感官刺激種類較多；要注意的是這些感覺包括了餘韻，不一定限制於喝時的當下感受。

複雜度（計算機複雜性理論）

計算複雜性理論（Computational complexity theory）是計算理論的一部分，研究計算問題時所需的資源，比如時間和空間，以及如何儘可能的節省這些資源。

計算複雜性理論所研究的資源中最常見的是時間複雜度（要通過多少步才能解決問題）和空間複雜度（在解決問題時需要多少內存）。其他資源亦可考慮，例如在並行計算中，需要多少並行處理器才能解決問題。

時間複雜度是指在計算機科學與工程領域完成一個算法所需要的時間，是衡量一個算法優劣的重要參數。時間複雜度越小，説明該算法效率越高，則該算法越有價值。

空間複雜度是指計算機科學領域完成一個算法所需要佔用的存儲空間，一般是輸入參數的函數。它是算法優劣的重要度量指標，一般來説，空間複雜度越小，算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有X個字（word）屬於這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。

複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種“矛”與“盾”的關係，即算法理論專注於設計有效的算法，而複雜性理論專注於理解為什麼對於某類問題，不存在有效的算法。

複雜度(Complexity, CPX) ^[1]  ：

複雜度的概念首先是由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)，這樣的結果比粗粒化複雜度更為精確。