算法的時間復(fù)雜度和空間復(fù)雜度

一個算法的好壞我們主要從"時間"和"空間" 兩個維度來衡量

時間維度：是指執(zhí)行當(dāng)前算法所消耗的時間，我們通常用 “時間復(fù)雜度” 來描述。

空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間，我們通常用 “空間復(fù)雜度” 來描述。

1. 時間復(fù)雜度

我們先來看一個簡單的例子

public class TimeCompare {public static void main(String[] args) {int num1=0;int num2=0;//計算1-1000的和-循環(huán)求和long start1 = System.currentTimeMillis();for(int i=1;i<=100000;i++){num1+=i;}long start2 = System.currentTimeMillis();//前n項和公式：(首項+末項)*項數(shù)/2long start3 = System.currentTimeMillis();num2=(1+100000)*100000/2;long start4 = System.currentTimeMillis();System.out.println("num1:"+num1+" 時間："+(start2-start1)+"ms");System.out.println("num2:"+num2+" 時間："+(start4-start3)+"ms");} }

結(jié)果：

num1:705082704 時間：3ms num2:705082704 時間：0ms

兩種方法都可以算出前n項和，但是時間上面卻是天壤之別

上面我們通過運行程序得到的時間并不能真正表示時間復(fù)雜度，因為程序的運行會受計算機和運行環(huán)境的影響

大O符號表示法：
我們一般用 “算法的漸進時間復(fù)雜度” 衡量時間復(fù)雜度 即：T(n) = O(f(n))

解釋： f(n) 表示每行代碼執(zhí)行次數(shù)之和

舉個栗子：

for(int i=0;i<n;i++){System.out.println("時間復(fù)雜度")}

時間復(fù)雜度為n，因為輸出語句會執(zhí)行n次

注意：我們求時間復(fù)雜度時，直接保留最高次的即可，并且最高次的系數(shù)可以省略，常數(shù)也可以省略

如：3n^2+2n+1我們會寫為：T(n)=n^2

常見的時間復(fù)雜度量級有：

• 常數(shù)階O(1) 只要沒有循環(huán)等復(fù)雜結(jié)構(gòu)就是常數(shù)階

• 對數(shù)階O(logN)

  //跳出循環(huán)需要 2^X=n 即 X=logN(2為底) 事件復(fù)雜度為：O(logN) int i = 1; while(i<n) {i = i * 2; }

• 線性階O(n) n次循環(huán)就是線性階

• 線性對數(shù)階O(nlogN) n次對數(shù)階

• 平方階O(n2)

• 立方階O(n3)

• K次方階O(n^k)

• 指數(shù)階(2^n)

從上到下時間復(fù)雜度依次變大，程序效率變低

2. 空間復(fù)雜度

空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢，我們用

S(n) =O(fn)來定義。

空間復(fù)雜度常用的有：O(1)、O(n)、O(n^2)、O(n^3)…

例：

算法執(zhí)行需要的臨時空間不會隨著某個變量n的變化而變化,

此時空間復(fù)雜度為常量：即S(n)=O(1)

//S(n)=O(1) int i=0; i++; int j=0,k=1; //空間復(fù)雜度為：S(n)=O(n) int[] arr=new int[n]; for(int i=0;i<arr.length;i++){arr[i]=i; }

空間復(fù)雜度再看只看占用空間(內(nèi)存)大小-即聲明的變量，和執(zhí)行次數(shù)無關(guān)

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。