本篇內(nèi)容主要講解“怎么理解Java算法復(fù)雜度”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“怎么理解Java算法復(fù)雜度”吧!
衡量時(shí)間復(fù)雜度通常使用”大O符號“。什么是大O符號？我們需要先看看一些數(shù)學(xué)知識：函數(shù)和極限。
00001. 一元二次函數(shù)f(x)=2x^2+2x+2;
00002. 當(dāng)x趨于無窮大的時(shí)候，記作x—>∞。
00003. x->∞，f(x)=2x^2+2x+2 = 2x^2 = 2x^2。
上述第3項(xiàng)，當(dāng)x無窮大的時(shí)候2x^2+2x+2約等于2x^2，在極限思想（算法分析）里面可以理解為2x^2+2x+2=2x^2。原因如下：
當(dāng)x=5的時(shí)候：
2x^2+2x+2=62.
2x^2=50.
當(dāng)x=500的時(shí)候：
2x^2+2x+2=501002
2x^2=250000.
通過上面的例子，繼續(xù)增大x的值，甚至無窮大的時(shí)候，f(x)函數(shù)中的2x+2這一項(xiàng)就可以忽略不計(jì)了。所以x->∞時(shí)，（2x^2+2x+2）約等（2x^2），或者（2x^2+2x+2）=（2x^2）。并且在極限思想里面，2x^2前面的系數(shù)2也是可以省略的。也就是說x->∞的時(shí)候，2x^2~x^2。
通過極限的思想，我們將函數(shù)f(x)=2x^2+2x+2，省略剩余項(xiàng)為x^2。也就是說x->∞時(shí)，f(x)=2x^2+2x+2=x^2；使用大O符號表示：x->無窮大，f(x)=O(x^2)。
大O是用來刻畫被截?cái)嗟臒o窮級數(shù)尤其是漸近級數(shù)的剩余項(xiàng)。大O符號表示函數(shù)的漸進(jìn)性上界。就好比上面的數(shù)學(xué)舉例，函數(shù)f(x)=2x^2+2x+2 漸進(jìn)級數(shù)的剩余項(xiàng)就是x^2，記作O(x^2)。也就是說O(x^2)是f(x)的漸進(jìn)性上界。
題目：求1+2+3+……+n的和。（高斯算法）
● 初級程序員的代碼：
… …
for (int i = 1; i <= n; i++) {
sum+=i;
}
… …
分析：
00001. 上述代碼中的sum+=1執(zhí)行多少次？ 答案：n次。
00002. int i=1執(zhí)行1次。
00003. i<=n執(zhí)行n+1次。（因?yàn)閒or循環(huán)執(zhí)行的順序，只有i大于n時(shí)才會停止循環(huán)，所以i=n+1的時(shí)候，還會再判斷一下i<=n，所以相比較而言會多執(zhí)行一次）。
00004. i++執(zhí)行n次。
匯總一下，上述代碼執(zhí)行n+1+n+1+n=3n+2次。
如果用極限思維，n->∞，3n+2 ~ 3n ~ n；記作O(n)。O(n)就是上述代碼的時(shí)間復(fù)雜度。
● 高級程序員的代碼：
… …
(1+n)*n/2
… …
如上，同樣的計(jì)算1加到n，采用高斯算法就簡單多了。上述代碼只需要執(zhí)行1次，沒有循環(huán)。所以時(shí)間復(fù)雜度就是O(1)。
● 小結(jié)
O(1)和O(n)的區(qū)別是什么呢？當(dāng)上述”初級程序員代碼“和”高級程序員代碼”中的變量n不斷增大的時(shí)候，高斯算法的時(shí)間復(fù)雜度基本不變，還是O(1)。但是“初級程序員代碼”的時(shí)間復(fù)雜度就會增加。
對于計(jì)算機(jī)來說，高斯算法求解1連續(xù)加到n的計(jì)算速度遠(yuǎn)遠(yuǎn)大于for循環(huán)的速度。速度越快，系統(tǒng)的性能就會越好。
到此，相信大家對“怎么理解Java算法復(fù)雜度”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
重慶分公司
重慶分公司
