演算法的時間復雜度分析

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

演算法的時間復雜度取決於問題的規模，待處理數據的初態。

一個語句的頻度是指該語句在演算法中被重復執行的次數。演算法中所有語句的頻度之和記為T(n)，它是該演算法問題規模n的函數，時間復雜度主要分析T(n)的數量級。演算法中基本運算（最深層循環內的語句）的頻度與Tn)同數量級，因此通常採用演算法中基本運算的頻度fn)來分析演算法的時間復雜度3。

演算法的時間復雜度記為：T(n)= O(fn))式中，О 的含義是T(n)的數量級，其嚴格的數學定義是:若T(n)和fn)是定義在正整數集合上的兩個函數，則存在正常數C和n，使得當n≥no時，都滿足0≤T(n)≤Cfn)。

演算法的時間復雜度不僅依賴於問題的規模n，也取決於待輸入數據的性質（如輸入數據元素的初始狀態)。

『貳』 演算法復雜度：時間復雜度和空間復雜度

本文部分摘抄於此
演算法復雜度分為時間復雜度和空間復雜度。
時間復雜度是指執行演算法所需要的計算工作量；
而空間復雜度是指執行這個演算法所需要的內存空間。
（演算法的復雜性體現在運行該演算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器）資源，因此復雜度分為時間和空間復雜度）。

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

在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(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)。

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

將基本語句執行次數的數量級放入大Ο記號中。

如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。

第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο( n 2)，則整個演算法的時間復雜度為Ο(n+ n 2)=Ο( n 2)。

Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。其中 Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3) 稱為多項式時間， 而Ο(2n)和Ο(n!)稱為指數時間 。計算機科學家普遍認為前者（即多項式時間復雜度的演算法）是有效演算法，把這類問題稱為 P（Polynomial,多項式）類問題 ，而把後者（即指數時間復雜度的演算法）稱為 NP（Non-Deterministic Polynomial, 非確定多項式）問題 。

（4）在計算演算法時間復雜度時有以下幾個簡單的程序分析法則:

(1).對於一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間

(2).對於順序結構,需要依次執行一系列語句所用的時間可採用大O下"求和法則"

求和法則:是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))

特別地, 若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))

(3).對於選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

(4).對於循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則"

乘法法則 : 是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則T1 * T2=O(f(n) * g(n))

(5).對於復雜的演算法,可以將它分成幾個容易估算的部分,然後利用求和法則和乘法法則技術整個演算法的時間復雜度

另外還有以下2個運演算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數

（5）下面分別對幾個常見的時間復雜度進行示例說明：

(1)、O(1)

​ Temp=i; i=j; j=temp;

以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。 注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

(2)、O(n2)

2.1. 交換i和j的內容

解： 因為Θ(2n2+n+1)=n2（Θ即：去低階項，去掉常數項，去掉高階項的常參得到），所以T(n)= =O(n2)；

2.2.

​

解： 語句1的頻度是n-1

一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分，當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

(3)、O(n)

解：

(4)、O(log2n)

解：

(5)、O(n3)

解：

（5）常用的演算法的時間復雜度和空間復雜度

一個經驗規則： 其中c是一個常量，如果一個演算法的復雜度為c 、 log2n 、n 、 n log2n ,那麼這個演算法時間效率比較高 ，如果是 2n * , 3n ,n!，那麼稍微大一些的n就會令這個演算法不能動了，居於中間的幾個則差強人意。

​ 演算法時間復雜度分析是一個很重要的問題，任何一個程序員都應該熟練掌握其概念和基本方法，而且要善於從數學層面上探尋其本質，才能准確理解其內涵。

2、演算法的空間復雜度

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

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。

演算法的輸入輸出數據所佔用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本演算法的不同而改變。存儲演算法本身所佔用的存儲空間與演算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的演算法。

演算法在運行過程中臨時佔用的存儲空間隨演算法的不同而異，有的演算法只需要佔用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種演算法是「就地"進行的，是節省存儲的演算法，如這一節介紹過的幾個演算法都是如此；

有的演算法需要佔用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將佔用較多的存儲單元，例如將在第九章介紹的快速排序和歸並排序演算法就屬於這種情況。

如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個演算法的空I司復雜度與n成線性比例關系時，可表示為O(n).

【1】如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

解答：
T(n)=O(1)，
這個程序看起來有點嚇人，總共循環運行了1100次，但是我們看到n沒有?
沒。這段程序的運行是和n無關的，
就算它再循環一萬年，我們也不管他，只是一個常數階的函數

【2】當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

該程序段中頻度最大的語句是(5)，內循環的執行次數雖然與問題規模n沒有直接關系，但是卻與外層循環的變數取值有關，而最外層循環的次數直接與n有關，因此可以從內層循環向外層分析語句(5)的執行次數：
則該程序段的時間復雜度為T(n)=O(n3/6+低次項)=O(n3)

【3】演算法的時間復雜度不僅僅依賴於問題的規模，還與輸入實例的初始狀態有關。

在數值A[0..n-1]中查找給定值K的演算法大致如下：

此演算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及K的取值有關:

（5）時間復雜度評價性能

有兩個演算法A1和A2求解同一問題，時間復雜度分別是T1(n)=100n2，T2(n)=5n3。
（1）當輸入量n＜20時，有T1(n)＞T2(n)，後者花費的時間較少。
（2）隨著問題規模n的增大，兩個演算法的時間開銷之比5n3/100n2=n/20亦隨著增大。
即當問題規模較大時，演算法A1比演算法A2要有效地多。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個演算法在時間方面的質量。

在演算法分析時，往往對演算法的時間復雜度和漸近時間復雜度不予區分，而經常是將漸近時間復雜度T(n)=O(f(n))簡稱為時間復雜度，其中的f(n)一般是演算法中頻度最大的語句頻度。

其實生活很美好，只是你想的太多了。沒有，不會，有差距很正常，因為我不會

『叄』 時間復雜度

求解演算法的時間復雜度的具體步驟是：

⑴ 找出演算法中的基本語句；

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

⑵ 計算基本語句的執行次數的數量級；

只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

⑶ 用大Ο記號表示演算法的時間性能。
將基本語句執行次數的數量級放入大Ο記號中。
果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：

第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。
Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。

其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者（即多項式時間復雜度的演算法）是有效演算法，把這類問題稱為P（Polynomial,多項式）類問題，而把後者（即指數時間復雜度的演算法）稱為NP（Non-Deterministic Polynomial, 非確定多項式）問題。

一般來說多項式級的復雜度是可以接受的，很多問題都有多項式級的解——也就是說，這樣的問題，對於一個規模是n的輸入，在n^k的時間內得到結果，稱為P問題。有些問題要復雜些，沒有多項式時間的解，但是可以在多項式時間里驗證某個猜測是不是正確。

4）在計算演算法時間復雜度時有以下幾個簡單的程序分析法則:

(1).對於一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間

(2).對於順序結構,需要依次執行一系列語句所用的時間可採用大O下"求和法則"

求和法則:是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))

特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))

(3).對於選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

(4).對於循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則"

乘法法則: 是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1 T2=O(f(n) g(n))

(5).對於復雜的演算法,可以將它分成幾個容易估算的部分,然後利用求和法則和乘法法則技術整個演算法的時間復雜度

另外還有以下2個運演算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數

簡單的說 就是可以將兩個演算法的時間復雜度 相加或相乘

(1)、O(1)

以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

(2)、O(n2)

2.1. 交換i和j的內容

解：因為Θ(2n2+n+1)=n2（Θ即：去低階項，去掉常數項，去掉高階項的常參得到），所以T(n)= =O(n2)；

去低階項，去掉常數項，去掉高階項的常參得到
該演算法的時間復雜度T(n)=O(n^2).

(3)、O(n)

T(n)=2+n+3(n-1)=4n-1=O(n).
該演算法程序的時間復雜度為 O(n)

後續更新

『肆』 如何分析演算法的復雜度

演算法的復雜性
演算法的復雜性是演算法效率度量，是評價演算法優劣的重要依據。一個演算法的復雜性的高低體現在運行該演算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該演算法的復雜性越高；反之，所需的資源越低，則該演算法的復雜性越低。
計算機的資源，最重要的是時間和空間（即存儲器）資源。因而，演算法的復雜性有時間復雜性和空間復雜性之分。
不言而喻，對於任意給定的問題，設計出復雜性盡可能低的演算法是我們在設計演算法時追求的一個重要目標；另一方面，當給定的問題已有多種演算法時，選擇其中復雜性最低者，是我們在選用演算法適應遵循的一個重要准則。因此，演算法的復雜性分析對演算法的設計或選用有著重要的指導意義和實用價值。
簡言之，在演算法學習過程中，我們必須首先學會對演算法的分析，以確定或判斷演算法的優劣。
1.時間復雜性：
例1：設一程序段如下（為討論方便，每行前加一行號）
(1) for i:=1 to n do
(2) for j:=1 to n do
(3) x:=x+1
......
試問在程序運行中各步執行的次數各為多少？
解答：
行號 次數(頻度)
(1) n+1
(2) n*(n+1)
(3) n*n
可見，這段程序總的執行次數是：f(n)=2n2+2n+1。在這里，n可以表示問題的規模，當n趨向無窮大時，如果 f(n)的值很小，則演算法優。作為初學者，我們可以用f(n)的數量級O來粗略地判斷演算法的時間復雜性，如上例中的時間復雜性可粗略地表示為T(n)=O(n2)。

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

演算法的時間復雜度取決於問題的規模，待處理數據的初態。

一個語句的頻度是指該語句在演算法中被重復執行的次數。演算法中所有語句的頻度之和記為T(n)，它是該演算法問題規模n的函數，時間復雜度主要分析T(n)的數量級。演算法中基本運算（最深層循環內的語句）的頻度與Tn)同數量級，因此通常採用演算法中基本運算的頻度fn)來分析演算法的時間復雜度3。

演算法的時間復雜度記為：T(n)= O(fn))式中，О 的含義是T(n)的數量級，其嚴格的數學定義是:若T(n)和fn)是定義在正整數集合上的兩個函數，則存在正常數C和n，使得當n≥no時，都滿足0≤T(n)≤Cfn)。

演算法的時間復雜度不僅依賴於問題的規模n，也取決於待輸入數據的性質（如輸入數據元素的初始狀態)。

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

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

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

相關介紹：

時間復雜度是同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。

空間復雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。而一般的遞歸演算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。

演算法的復雜性體現在運行該演算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器）資源，因此復雜度分為時間和空間復雜度。

『柒』 演算法時間復雜度分析

這里我們只列舉一些簡單的演算法時間復雜度分析

一重循環的時間復雜度為0(n)。

二重循環的時間復雜度為0(n ² )。

三重循環的時間復雜度為0(n ³ )。以此類推。

舉個簡單的例子

看了這個你大概就能估算出log的數大概有多大。根據評測機的運算速度判斷是否超時。

int的范圍為-2147483648~2147483647。大概在±2×10 ⁹

long long的范圍大概在±10 ¹⁸

應該記一下的一些數的次方。

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

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

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

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

『玖』 遞歸演算法時間復雜度怎麼分析

1、遞歸
是指對一個問題的求解，可以通過同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出復雜形式的解. 遞歸是解決一類問題的重要方法. 遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的. 但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省. 以下討論遞歸的時間效率分析方法，以及與非遞歸設計的時間效率的比較.
2 時間復雜度的概念及其計算方法
演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價准則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程序在計算機中運行的時間來衡量，所花費的時間與演算法的規模n有必然的聯系，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量.
演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重復執行的次數）來估算的，它是問題規模n的某一個函數f(n). 演算法時間度量記作：T（n）=O（f（n））
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間復雜度，簡稱時間復雜度[2].
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程序段中，語句x=x+1的頻度分別為1，n，n2，則這三段程序的時間復雜度分別為O（1），O（n），O（n2）.
求解過程為：先給出問題規模n的函數的表達式，然後給出其時間復雜度T（n）.
但是在現實程序設計過程中，往往遇到的問題都是比較復雜的演算法，就不能很容易地寫出規模n的表達式，也比較難總結其時間復雜度. 遞歸函數就是屬於這種情況. 下面舉例說明遞歸函數的時間復雜度的分析方法.

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

演算法的時間復雜度是指演算法在編寫成可執行程序後，運行時所需要的資源，資源包括時間資源和內存資源。

一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

時間復雜度：

（1）時間頻度：一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。

並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。演算法的時間復雜度是指執行演算法所需要的計算工作量。

（2）時間復雜度：在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。