算法定義

? ?算法由控制結構（順序、分支和循環3種）和原操作（指固有數據類型的操作）構成的，則算法時間取決于兩者的綜合效果。為了便于比較同一個問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作的重復執行的次數作為算法的時間量度。不同的算法可能用不同的時間、空間或效率來完成同樣的任務，一個算法的優劣可以用空間復雜度與時間復雜度來衡量.

時間復雜度

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

2、時間復雜度：在時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什么規律。為此，我們引入時間復雜度概念。 一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n))?為算法的漸進時間復雜度，簡稱時間復雜度。此外，T (n) = Ο(f (n))?表示存在一個常數C，使得在當n趨于正無窮時總有?T (n) ≤ C * f(n)。簡單來說，就是T(n)在n趨于正無窮時最大也就跟f(n)差不多大。也就是說當n趨于正無窮時T (n)的上界是C * f(n)。其雖然對f(n)沒有規定，但是一般都是取盡可能簡單的函數。例如，O(2n²+n +1) = O (3n²+n+3) = O (7n²?+ n) =?O (?n²?)?，一般都只用O(n²)表示就可以了。注意到大O符號里隱藏著一個常數C，所以f(n)里一般不加系數。如果把T(n)當做一棵樹，那么O(f(n))所表達的就是樹干，只關心其中的主干，其他的細枝末節全都拋棄不管。

常見的數量級大小：O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2n2)＜O(n3n3)＜O(2n2n)＜O(n!)

數量級能承受的大致規模常見算法

O(1)	任意	直接輸出結果
O(logn)	任意	二分查找、快速冪
O(n)	以百萬計（五六百萬）	貪心算法、掃描和遍歷
O(nlogn)	以十萬計（三四十萬）	帶有分治思想的算法，如二分法
O(n2)	以千計數（兩千）	枚舉、動態規劃
O(n3)	不到兩百	動態規劃
O(2n)	24	搜索
O(n!)	10	產生全排列
O(nn)	8	暴力法破解密碼

O(1)叫常數時間；O(n)、O(n²)、O(n³)、O(n⁴)……叫做多項式時間；O(2ⁿ)、O(3ⁿ)……叫做指數時間。

3、算法的時間復雜度的具體步驟：

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

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

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

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

　?、?用大Ο記號表示算法的時間性能。

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

　　如果算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果算法中包含并列的循環，則將并列循環的時間復雜度相加。舉個例子：第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n²)，則整個算法的時間復雜度為Ο(n+n²)=Ο(n²)。

let x =1; let y = 1; for (let i=1; i<=n; i++) {x++; } for (let j=1; j<=m; i++){for (let k=1; k<=m; j++) {y++; } }

4、常見的時間復雜度進行示例

（1）O(1)

　　let x=1;

? (2) O(n)

sum=0； （1次） for(i=1;i<=n;i++) { （n+1次） sum++； (n+1次) }

　　

　　Θ(2n+2)=n? （Θ即：去低階項，去掉常數項，去掉高階項的常參得到），所以

?

?

let sum=0； (1次） for(let i=1;i<=n;i++) （n+1次） for(let j=1;j<=n;j++) （(n+1)(n+1)次） sum++； （(n+1)(n+1)次）

　　

　　Θ(2n²+5n+3)=n^2?T(n)=O(n²)；

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

? （4）O(log₂n)??

　　

i = 1; while(i<=n){i = i*2; }

　　

　　

　　 i = 2, 4, 8,?16 ，32，64，128? => i = 2^x,?假設x次(時間頻度)后跳出循環，因為 i<=n ，所以2^x <= n => x = log₂n

? ? 所以 T(n) = O(?log₂n)

while(n){n = n/2; }

　　

　　128，64，32，16，8，4，2，...

? ?=> 2^x? = n => x =?log₂n

? ?（5）O(n³)?

　　　

for(i=0;i<n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) x=x+2; } }

　　O(n³)

?

?

?

?

轉載于:https://www.cnblogs.com/xiaosongJiang/p/10003399.html

總結

以上是生活随笔為你收集整理的算法的时间和空间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。