Java二十七：時間 / 空間復雜度分析
數(shù)據(jù)結(jié)構(gòu)應(yīng)該知道的相關(guān)知識
我也在工作中學習的數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)知識，視頻地址：
https://www.bilibili.com/video/BV1E4411H73v?p=2
時間/空間復雜度：數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題，即如何讓代碼運行得更快，如何讓代碼更省存儲空間。
我們都知道同一個問題有不同的算法解決，這些算法在運行時間、運行占用內(nèi)存、代碼易讀性等方面都不相同，而在這些算法中，我們只能選擇一種解決方案，這時判斷選擇哪個算法的依據(jù)是什么呢？
在這里，我們引入了時間復雜度和空間復雜度這兩個概念作為選擇適合算法的重要依據(jù)，一般對比算法的好壞基本上從它的時間復雜度和空間復雜度來綜合判斷就可以得出哪個更適合，復雜度通常來說越小越好。
算法的時間復雜度和空間復雜度的作用：時間復雜度是指執(zhí)行這個算法所需要的計算工作量；而空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。時間和空間（即寄存器）都是計算機資源的重要體現(xiàn)，而算法的復雜性就是體現(xiàn)在運行該算法時的計算機所需的資源多少。
時間復雜度 （Time complexity）
一個算法語句總的執(zhí)行次數(shù)是關(guān)于問題規(guī)模N的某個函數(shù)，記為f(N)，N稱為問題的規(guī)模。語句總的執(zhí)行次數(shù)記為T(N)，當N不斷變化時，T(N)也在變化，算法執(zhí)行次數(shù)的增長速率和f(N)的增長速率相同。
則有T(N) = O(f(N))，這稱作算法的漸進時間復雜度，簡稱時間復雜度。
1、算法的時間復雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級，在很大程度上能很好地反映出算法的優(yōu)劣與否。
2、算法執(zhí)行時間需要依據(jù)該算法編制的程序在計算機上執(zhí)行運行時所消耗的時間來度量，度量方法有兩種：事后統(tǒng)計方法和事前分析估算方法。因為事后統(tǒng)計方法更多地依賴計算機的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)劣，因此常采用事前分析估算的方法。
3、一個算法是由控制結(jié)構(gòu)（順序、分支、循環(huán)三種）和原操作（固有數(shù)據(jù)類型的操作）構(gòu)成的，而算法時間取決于兩者的綜合效率。
4、一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比，執(zhí)行次數(shù)越多，花費的時間就越多，其執(zhí)行次數(shù)稱為語句頻度或時間頻度，記為T（n）。
5、在時間頻度中，n為問題的規(guī)模，當n不斷變化時，它所呈現(xiàn)出來的規(guī)律，我們稱為時間復雜度。
6、在各種算法中，若算法中的語句執(zhí)行次數(shù)為一個常數(shù)，則時間復雜度為o（1），同時，若不同算法的時間頻度不一樣，但他們的時間復雜度卻可能是一樣的。比如：T(n)=n^2+2n+4 ?與 T（n）=4n^2+n+8，他們的時間頻度顯然不一樣，但他們的時間復雜度卻是一樣的，均為O(n^2)，時間復雜度只關(guān)注最高數(shù)量級，且與之系數(shù)也沒有關(guān)系。
最壞時間復雜度和平均時間復雜度
最壞情況下的時間復雜度稱最壞時間復雜度，一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何更長。
平均時間復雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間，設(shè)每種情況的出現(xiàn)的概率為pi,平均時間復雜度則為sum(pi*f(n)) 。
求解算法的時間復雜度的具體步驟
⑴ 找出算法中的基本語句
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。
⑵ 計算基本語句的執(zhí)行次數(shù)的數(shù)量級
只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。
⑶ 用大Ο記號表示算法的時間性能
將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中，如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體；如果算法中包含并列的循環(huán)，則將并列循環(huán)的時間復雜度相加。
下面舉一個簡單例子：
for (i = 1; i <= n; i++) {
? ? ? ? ? ?a++;
? ? ? ?};
? ? ? ?for (i = 1; i <= n; i++) {
? ? ? ? ? ?for (j = 1; j <= n; j++) {
? ? ? ? ? ? ? ?a++;
? ? ? ? ? ?}
? ? ? ?}
第一個for循環(huán)的時間復雜度為o（n），第二個for循環(huán)時間復雜度為o（n^2），則整個算法的時間復雜度為o(n^2+n)。
o(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)，一般來說，只要算法中不存在循環(huán)語句，時間復雜度就為o(1)。
時間復雜度的分析方法
1、時間復雜度就是函數(shù)中基本操作所執(zhí)行的次數(shù)
2、一般默認的是最壞時間復雜度，即分析最壞情況下所能執(zhí)行的次數(shù)
3、忽略掉常數(shù)項
4、關(guān)注運行時間的增長趨勢，關(guān)注函數(shù)式中增長最快的表達式，忽略系數(shù)
5、計算時間復雜度是估算隨著n的增長函數(shù)執(zhí)行次數(shù)的增長趨勢
6、遞歸算法的時間復雜度為：遞歸總次數(shù) * 每次遞歸中基本操作所執(zhí)行的次數(shù)
7、常用的時間復雜度有以下七種，算法時間復雜度依次增加：O(1)常數(shù)型、O(log2 n)對數(shù)型、O(n)線性型、O(nlog2n)二維型、O(n^2)平方型、O(n^3)立方型、O(2^n)指數(shù)型.
1、Big O notation（最常見的7種復雜度）
O(1): Constant Complexity 常數(shù)復雜度
O(log n): Logarithmic Complexity 對數(shù)復雜度
O(n): Linear Complexity 線性時間復雜度
O(n^2): N square Complexity 平方
O(n^3): N cube Complexity 立方
O(2^n): Exponential Growth 指數(shù)
O(n!): Factorial 階乘
Notice：
只看最高復雜度的運算
常數(shù)系數(shù)不用考慮
特殊時間復雜度
1.二分查找
因為每次的計算，都可以把查找的范圍縮小一半，所以二分查找的時間復雜度為O（log2 N)。
2.斐波那契的遞歸算法
因為每次的展開都要把當前的已知項再拆分成當前數(shù)目的兩倍，所以斐波那契的遞歸算法時間復雜度為2^N。
斐波那契的時間復雜度算法如下圖所示，計算n第N個斐波那契數(shù)的大小時，共需計算2^N - 1次。
用排序算法的時間復雜度
空間復雜度（Space Complexity）
一個程序的空間復雜度是指運行完一個程序所需內(nèi)存的大小，利用程序的空間復雜度，可以對程序的運行所需要的內(nèi)存多少有個預(yù)先估計。一個程序執(zhí)行時除了需要存儲空間和存儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為現(xiàn)實計算所需信息的輔助空間。程序執(zhí)行時所需存儲空間包括以下兩部分。
（1）固定部分：這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)，主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡單變量）等所占的空間，這部分屬于靜態(tài)空間。
（2）可變空間：這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等，這部分的空間大小與算法有關(guān)。一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n))，其中n為問題的規(guī)模，S(n)表示空間復雜度。
1、空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。
2、一個算法在計算機上占用的內(nèi)存包括：程序代碼所占用的空間、輸入輸出數(shù)據(jù)所占用的空間、輔助變量所占用的空間這三個方面。程序代碼所占用的空間取決于算法本身的長短，輸入輸出數(shù)據(jù)所占用的空間取決于要解決的問題，是通過參數(shù)表調(diào)用函數(shù)傳遞而來，只有輔助變量是算法運行過程中臨時占用的存儲空間，與空間復雜度相關(guān)。
3、通常來說，只要算法不涉及到動態(tài)分配的空間以及遞歸、棧所需的空間，空間復雜度通常為0(1)。
4、算法的空間復雜度并不是計算實際占用的空間，而是計算整個算法的輔助空間單元的個數(shù)，與問題的規(guī)模沒有關(guān)系。
特殊空間復雜度
在斐波那契數(shù)求空間復雜度的過程中，我們需要考慮函數(shù)棧幀的過程，比如當我們求第五個斐波那契數(shù)的時候，這時候需要先開辟空間存放第四個數(shù)，然后再開辟空間存放第三個數(shù)；當開辟空間到第二個和第一個數(shù)的時候，第三個數(shù)得到結(jié)果并返回到第四個數(shù)中，第四個數(shù)的值已知后返回到第五個數(shù)中，在這個過程中，最大占用空間即為層數(shù)減一。如下圖所示：
開辟空間的大小最多等于層數(shù)+1，也就是說求第N個斐波那契數(shù)，空間復雜度即為O（N）。
二分查找因為整個運算過程沒有空間的改變，所以空間復雜度為O（1）。
時間復雜度與空間復雜度的聯(lián)系
對于一個算法，其時間復雜度和空間復雜度往往是相互影響的。當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間;反之，當追求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間。
總結(jié)：
1.對于一個算法，算法的時間復雜度和空間復雜度往往是相互影響的，其所有性能之間都存在著或多或少的相互影響，因此，當設(shè)計一個算法(特別是大型算法)時，要綜合考慮算法的各項性能、算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性、算法運行的機器系統(tǒng)環(huán)境等各方面因素，才能夠設(shè)計出比較好的算法。
2.不管是刷題，還是在平時工作中寫代碼，我們對自己寫出來的代碼的時間復雜度和空間復雜度應(yīng)當有所理解，對代碼消耗的內(nèi)存和花費的時間有個底。時間復雜度和空間復雜度都需要根據(jù)場景變化而變化。比如響應(yīng)速度快的，通常用空間換時間的原則；內(nèi)存放不下，就適當放寬時間復雜度來換內(nèi)存的優(yōu)化。設(shè)計代碼就是對時間、空間、開發(fā)成本各種要素的平衡，盡可能取到最優(yōu)化的策略。
3.復雜度用來分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模增長的變化關(guān)系，越高階復雜度的的算法執(zhí)行效率也就越低，上面列舉的復雜度級別從低到高分別為O(1)、O(logn)、O(n)、O(nlogn)、O(n2)．
