java 空间复杂度_时间复杂度和空间复杂度
原文首發于微信公眾號：躬行之(jzman-blog)
時間復雜度和空間復雜度可以幫助我們根據具體的平臺選擇合適的算法，要學會以空間換時間或以時間換空間的設計思想，如在單片機等一般是內存空間比較緊張，在追求最優算法時應該可以適當以時間來換空間進行設計，當然在大內存設備上可以選擇以空間換時間的設計思想來設計最優算法，所以，時間和空間復雜度可在一定的限制條件下作為判斷某個算法或代碼塊運行快慢的判斷方式，主要從如下幾個方面了解和學習時間和空間復雜度：
數據結構與算法關系
時間復雜度
空間復雜度
總結
數據結構與算法關系
數據結構指一組數據的存儲結構，而算法是操作數據的一組方法，所以數據結構為算法服務，算法作用于特定的數據結構。
數據結構與算法關系
大O復雜度表示法
大O復雜度表示法可以粗略的了解代碼運行的時間效率，比如下面這段代碼：
int?cal(int?n)?{
int?sum?=?0;
int?i?=?1;
for?(;?i?<=?n;?++i)?{
sum?=?sum?+?i;
}
return?sum;
}
復制代碼
假如有效代碼(有賦值操作)每一行的執行時間為一個單位時間，那么上述代碼的執行時間可表示為 2n + 2 個單位時間，這里可以看出代碼執行時間與每行有效代碼執行的次數成正比。
如果是下面這段代碼：
int?cal(int?n)?{
int?sum?=?0;
int?i?=?1;
int?j?=?1;
for?(;?i?<=?n;?++i)?{
j?=?1;
for?(;?j?<=?n;?++j)?{
sum?=?sum?+??i?*?j;
}
}
}
復制代碼
在假設條件下上述代碼的執行時間可表示為 2n*n + 2n + 3，這里也可以看出代碼執行時間與每行有效代碼執行的次數成正比，使用公式可表示為：
T(n)?=?O(n)
復制代碼
則上述兩段代碼執行時間與代碼執行次數之間的關系可以表示為：
T(n)?=?O(2n?+?2)
T(n)?=?O(?2n*n?+?2n?+?3)
復制代碼
隨著數據規模的增大，后面的常數項不會影響代碼執行時間隨數據規模增長的變化趨勢，上面兩個函數很明顯一個是線性函數，一個是二次函數，隨著 n 的增大，最終二次函數的值會超過一次函數，所以我們取最高階來作比較，去除其他的次要向，簡化后如下：
T(n)?=?O(n)
T(n)?=?O(n*n)
復制代碼
現在就可以說上述兩段代碼的時間復雜度用大O表示法可表示為 O(n) 和 O(n*n)。
時間復雜度
時間復雜度：從上面得出的結論，我們知道使用大O表示法表明的是該段代碼執行時間隨數據規模增大的變化趨勢，大O表示法的假設前提是隨著數據規模的增大，只保留最高階項就能估算代碼運行的時間復雜度，所以在進行復雜度分析時，只關注量級最大的時間復雜度即可。
常見的時間復雜度量級從小到大依次是：
常數階(O(1))?
復制代碼
上面的量級中階乘階、次方階都屬于非多項式量級，當數據規模急劇增大時，非多項式量級算法執行時間越來越長，這種算法也是最低效的算法，下面說明一下多項式量級的注意點。
O(n)：無論有多少行代碼，只有執行次數能確定，那么它的時間復雜度量級就表示為 O(1)，不會出現 O(2)、O(3)等其他情況。
O(logn)：對數時間復雜度計算主要是找到滿足的條件，計算代碼運行的次數，即代碼運行多少次才能執行完，舉例如下：
i=1;
while?(i?<=?n)??{
i?=?i?*?2;
}
復制代碼
如上述代碼，我們只要知道這段代碼執行多少次執行完就可以了，也就是找到 i 與 n 的關系，i 的值依次是 1、2、8、16 等，也就是 2^0、2^1、2^3、2^4等，所以 i 與 n 的關系 2^t = n，然后計算出 t 的再剔除無關項的時間復雜度就是對數時間復雜度。當然線性對數階 O(nlogn) 就是將上述代碼循環 n 次的結果。
O(m+n)：如下面這段代碼在表示復雜度的時候就不能直接相加去最高階了：
int?cal(int?m,?int?n)?{
int?sum_1?=?0;
int?i?=?1;
for?(;?i?
sum_1?=?sum_1?+?i;
}
int?sum_2?=?0;
int?j?=?1;
for?(;?j?
sum_2?=?sum_2?+?j;
}
return?sum_1?+?sum_2;
}
復制代碼
m 和 n 表示兩個數據規模，我們無法確定 m 和 n 誰的量級大，此時的時間復雜度就表示為 O(m) + O(n)，如果 sum_1 * sun_2 則相應的時間復雜度表示為 O(m) * O(n)。
時間復雜度分析基本如上，下面來繼續看一下如下特殊情況復雜度分析，分析一下下面代碼的時間復雜度：
//?n?表示數組?array?的長度
int?find(int[]?array,?int?n,?int?x)?{
int?i?=?0;
int?pos?=?-1;
for?(;?i?
if?(array[i]?==?x)?pos?=?i;
}
return?pos;
}
復制代碼
分析過程：i 和 pos 的賦值操作共 2 次，不會影響代碼執行時間隨數據規模增大的趨勢變化可忽略，在 for 循環中，如果 i 增加到 m 的時候，滿足 for 循環里面的 if 語句中的條件，則此時的時間復雜度表示為 (1+m)n，所以該段代碼的事件復雜度一定是 O(n)，因為 if 語句在找到與 x 相等的值的時候還是沒有退出 for 循環，修改代碼如下：
//?n?表示數組?array?的長度
int?find(int[]?array,?int?n,?int?x)?{
int?i?=?0;
int?pos?=?-1;
for?(;?i?
if?(array[i]?==?x)?{
pos?=?i;
break;
}
}
return?pos;
}
復制代碼
如果在找到數組中與 x 的值相等的值就退出循環，此時對于事件復雜度 (1+m)n 就有兩種可能，一種是能找到符合 if 語句條件的值退出循環，此時 m 一定是常量值可以忽略，此時這段代碼的復雜的就是 O(1)，當然如果已知不滿足 if 語句的判斷條件，一直循環 n 次，此時這段代碼的事件復雜度還是 O(n)，可見同一段代碼在不同的條件下可能會有不同的時間復雜度，鑒于這種情況，將時間復雜度細化為三種：
最好情況時間復雜分析：指理想情況下執行某段代碼的復雜度，對應上述代碼就是當在數組中找到滿足 if 語句條件的值的時候，上述代碼的時間復雜度就是 O(1) 就是最好時間復雜度；
最壞情況時間復雜分析：指最糟糕情況下執行某段代碼的復雜度，對應上述代碼就是永遠在數組中找不到滿足條件的退出 for 循環，此時上述代碼的時間復雜度就是 O(n) 就是最壞時間復雜度；
空間復雜度
空間復雜度反映的是存儲空間隨數據規模增長趨勢，如下面這段代碼：
void?print(int?n)?{
int?i?=?0;//棧內存
int[]?a?=?new?int[n];//堆內存
for?(i;?i?
a[i]?=?i?*?i;
}
}
復制代碼
上面代碼中關于內存申請的代碼只有兩處，其中變量 i 所占內存空間是固定的，忽略不計，其中數組的聲明申請了內存，而且大小還是 n 個 int 型所占內存的大小，所以此段代碼的空間復雜度為 O(n)。
總結
時間復雜度反映代碼執行時間隨數據規模增長的變化趨勢，重點關注循環嵌套等，空間復雜度反映存儲空間隨數據規模增長的變化趨勢，時間復雜度相較空間復雜度更常用，開發常說的復雜度如果不指定一般說的都是時間復雜度。此外，針對一段特定代碼，還可以細化為最好情況時間復雜度、最壞情況時間復雜度、平均時間復雜度和均攤時間復雜度，分析思路基本一樣，只是限制條件不同。
總結
以上是生活随笔為你收集整理的java 空间复杂度_时间复杂度和空间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： kl距离 java_信息量、熵、最大熵、
- 下一篇： JAVA爬虫https_java爬虫问题