如何判斷程序的復雜程度：時間和空間復雜度

1、如何判斷程序的復雜程度：時間和空間復雜度時間復雜度：使用大O表示法來表示程序的時間復雜度常見的7種時間復雜度(復雜度由低到高排序)0(1):常數時間復雜度O(log(n):對數時間復雜度O(n):線性時間復雜度0(nA2):平方時間復雜度0(nA3):立方時間復雜度0(n):指數時間復雜度，k表示常數0(n!):階乘時間復雜度ps：這里我們并不考慮前邊的系數；0(1)并不表示復雜度為1,也可以是2、3等常數；0(n)表示程序運行了n次或者2n、3n次；以此類推其他時間復雜度時間復雜度的判斷，以一段代碼的最高復雜度為準；如何判斷一段代碼的時間復雜度簡而言之就是看內部某段代碼的執(zhí)行次數0(1):常

2、數復雜度intn=1;System.out.println(n);12intn=1;System.out.println(n);System.out.println(n+1)System.out.println(n+2)12340(n):線性時間復雜度for(intj=0;jn;j+)System.out.println(j);123for(inti=0;in;i+)System.out.println(i);for(intj=0;jn;j+)System.out.println(j);1234560(nA2):平方時間復雜度for(inti=0;in;i+)for(intj=0;jn;j+)

3、System.out.println(i+j);12345O(nA3):立方時間復雜度for(inti=0;in;i+)for(intj=0;jn;j+)for(intk=0;kn;k+)System.out.println(i+j);1234567O(log(n)：對數時間復雜度這里演示的是以2為底n的對數for(inti=0;in;i=i*2)System.out.println(i);1230(2切)：指數時間復雜度/*遞歸求斐波那契數列的第n項；可以通過畫運行樹的方式獲得時間復雜度*/intfib(intn)if(n2)returnn;returnfib(n-1)+fib(n-2);1

4、234567O(n!):階乘時間復雜度todo小練習1:求和計算1n的和O(n)inty=2;for(inti=0;in;i+)y+=i;1234O(1)使用了求和公式：sum=n(n+1)/2inty=2;for(inti=0;in;i+)y+=i;1234小練習2:求斐波那契數列O(2An):intfib(intn)if(n2)returnn;returnfib(n-1)+fib(n-2);1234O(n):該方法比遞歸要快得多intfib2(intn)if(n=1|n=2)return1;inta=1,b=1,result=0;for(inti=3;i=n;i+)result=a+b;a

5、=b;b=result;returnresult;123456789101112主定理主定理(英語：mastertheorem)提供了用漸近符號(大O符號)表示許多由分治法得到的遞推關系式的方法常用算法中的應用算法遞回關系式運算時間二分搜尋算法二叉樹遍歷最佳排序矩陣搜索(已排好序的二維矩陣)合并排序所有排序的最優(yōu)算法都是O(nlog(n)空間復雜度如何判斷一段代碼的空間復雜度主要通過兩部分進行判斷：數組的長度如果代碼中應用了數組，那么數組的長度，基本上就是空間復雜度；e：維數組的空間復雜度是O(n);二維數組的空間復雜度是O(n)遞歸的深度如果代碼中有遞歸，那么遞歸的深度，就是代碼的空間復雜度的最大值ps:如果代碼中既有數組，又有遞歸，那么兩者的最大值就是代碼的空間復雜度leecode有個爬樓梯的復雜度分析情況；可以進行練習數組和鏈表的時間復雜度分析數組隨機增加：O(n)隨機查詢：O(1)隨機刪除：O(n)鏈表隨機增加：O(1)隨機查詢：O(n)隨機刪除：O(1)跳表跳躍表(skiplist)是一種隨機化的數據，由WilliamPugh在論文Skiplists:aprobabilisticalternativetobalancedtrees中提出，跳躍表以有序的方式在層次化的鏈表中保存元素，效率