時間復雜度演算法

『壹』 時間復雜度怎麼算

時間復雜度是評估演算法運行時間效率的一個指標。在計算機科學中，常用大 O 表示法（Big O Notation）來描述時間復雜度。假設演算法中需要進行 n 次操作，並且每次操作的時間為 t，則該演算法的時間復雜度可以表示為 O(n*t)。

常見的演算法時間復雜度包括：

• 常數階：O(1)。無論數據量大小，該演算法執行時間相同。

• 線性階：O(n)。隨著數據量的增加，算散羨掘法執行的時間也會線性增長。

• 對數階：O(logn)。演算法執行時間沖核隨著數據的增加而增長，但增長緩慢。

在實際開發和分析中，需要評估演算法的時間復雜度，並根據數據情況選擇適當的演算法，以達到更好的運行效率。

『貳』 什麼是演算法的時間復雜度

演算法的時間復雜度是一個函數，它定性描述該演算法的運行時間。

這是一個代表演算法輸入值的字元串的長度的函數。時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。

演算法的時間復雜度取決於什麼

演算法的時間復雜度取決於待處理數據的狀態以及問題的規模。演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

『叄』 演算法的時間復雜度是什麼

執行一個演算法所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。一個演算法花費的時間與演算法中語句的執行次數成正比例，演算法中哪個語句的執行次數多，它花費的時間就多。

1.語句頻度在演算法中一個語句的執行次數稱為語句頻度或時間頻度，記為T（n）。

2）演算法的漸進時間復雜度一般情況下，演算法的執行時間T是問題規模n的函數，記作T（n）。要精確地表示演算法的運行時間函數常常是很困難的，即使能夠給出，也可能是個相當復雜的函數，函數的求解本身也是相當復雜的。為了客觀地反映一個演算法的執行時間，可以用演算法中基本語句的執行次數的數量級來度量演算法的工作量，稱作演算法的漸進時間復雜度，簡稱時間復雜度，通常用O來表示。

『肆』 如何計算時間復雜度

1、先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））。

2、舉例

for（i=1;i<=n;++i）

{for(j=1;j<=n;++j)

{c[ i ][ j ]=0; //該步驟屬於基本操作 執行次數：n的平方次

for(k=1;k<=n;++k)

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 執行次數：n的三次方次}}

則有 T（n）= n的平方+n的三次方，根據上面括弧里的同數量級，我們可以確定 n的三次方為T（n）的同數量級

則有f（n）= n的三次方，然後根據T（n）/f（n）求極限可得到常數c

則該演算法的 時間復雜度：T（n）=O（n的三次方）

),線性階O(n),線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

關於對其的理解

《數據結構（C語言版）》 ------嚴蔚敏 吳偉民編著 第15頁有句話「整個演算法的執行時間與基本操作重復執行的次數成正比。」

基本操作重復執行的次數是問題規模n的某個函數f(n)，於是演算法的時間量度可以記為：T(n) = O(f(n))

如果按照這么推斷，T(n)應該表示的是演算法的時間量度，也就是演算法執行的時間。

而該頁對「語句頻度」也有定義：指的是該語句重復執行的次數。

如果是基本操作所在語句重復執行的次數，那麼就該是f(n)。

上邊的n都表示的問題規模。

『伍』 演算法時間復雜度指的是什麼

時間復雜性，又稱時間復雜度，演算法的時間復雜度是一個函數，它定性描述該演算法的運行時間。這是一個代表演算法輸入值的字元串的長度的函數。時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸進的，亦即考察輸入值大小趨近無窮時的情況。

空間復雜性介紹

空間復雜性是指計算所需的存儲單元數量。隸屬於計算復雜性（計算復雜性由空間復雜性和時間復雜性兩部分組成）。演算法的復雜性是演算法運行所需要的計算機資源的量，需要時間資源量稱為時間復雜性，需要空間資源的量成為空間復雜性。

一個演算法的空間復雜度S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。演算法的時間復雜度和空間復雜度合稱為演算法的復雜度。

『陸』 演算法的時間復雜度是指什麼

演算法的時間復雜度是指：執行程序所需的時間。

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近無窮大時。

T(n)/f(n)的極限值為不等於零的常數，則稱為f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間復雜度，簡稱時間復雜度。比如：

在 T(n)=4nn-2n+2 中，就有f(n)=nn，使得T(n)/f(n)的極限值為4，那麼O(f(n))，也就是時間復雜度為O(n*n)。

時間復雜度中大O階推導是：

推導大O階就是將演算法的所有步驟轉換為代數項，然後排除不會對問題的整體復雜度產生較大影響的較低階常數和系數。

有條理的說，推導大O階，按照下面的三個規則來推導，得到的結果就是大O表示法：運行時間中所有的加減法常數用常數1代替。只保留最高階項去除最高項常數。

其他常見復雜度是：

f(n)=nlogn時，時間復雜度為O(nlogn)，可以稱為nlogn階。

f(n)=n³時，時間復雜度為O(n³)，可以稱為立方階。

f(n)=2ⁿ時，時間復雜度為O(2ⁿ)，可以稱為指數階。

f(n)=n!時，時間復雜度為O(n!)，可以稱為階乘階。

f(n)=(√n時，時間復雜度為O(√n)，可以稱為平方根階。