怎么理解Java算法復(fù)雜度-創(chuàng)新互聯(lián)

本篇內(nèi)容主要講解“怎么理解Java算法復(fù)雜度”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“怎么理解Java算法復(fù)雜度”吧!

專注于為中小企業(yè)提供成都做網(wǎng)站、網(wǎng)站建設(shè)服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)玉環(huán)免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

大O符號

衡量時間復(fù)雜度通常使用”大O符號“。什么是大O符號？我們需要先看看一些數(shù)學(xué)知識：函數(shù)和極限。

2.1、數(shù)學(xué)舉例：

00001. 一元二次函數(shù)f(x)=2x^2+2x+2;

00002. 當(dāng)x趨于無窮大的時候，記作x—>∞。

00003. x->∞，f(x)=2x^2+2x+2 = 2x^2 = 2x^2。

上述第3項，當(dāng)x無窮大的時候2x^2+2x+2約等于2x^2，在極限思想（算法分析）里面可以理解為2x^2+2x+2=2x^2。原因如下：

當(dāng)x=5的時候：

2x^2+2x+2=62.

2x^2=50.

當(dāng)x=500的時候：

2x^2+2x+2=501002

2x^2=250000.

通過上面的例子，繼續(xù)增大x的值，甚至無窮大的時候，f(x)函數(shù)中的2x+2這一項就可以忽略不計了。所以x->∞時，（2x^2+2x+2）約等（2x^2），或者（2x^2+2x+2）=（2x^2）。并且在極限思想里面，2x^2前面的系數(shù)2也是可以省略的。也就是說x->∞的時候，2x^2~x^2。

通過極限的思想，我們將函數(shù)f(x)=2x^2+2x+2，省略剩余項為x^2。也就是說x->∞時，f(x)=2x^2+2x+2=x^2；使用大O符號表示：x->無窮大，f(x)=O(x^2)。

2.2、概念

大O是用來刻畫被截斷的無窮級數(shù)尤其是漸近級數(shù)的剩余項。大O符號表示函數(shù)的漸進性上界。就好比上面的數(shù)學(xué)舉例，函數(shù)f(x)=2x^2+2x+2 漸進級數(shù)的剩余項就是x^2，記作O(x^2)。也就是說O(x^2)是f(x)的漸進性上界。

時間復(fù)雜度

題目：求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次。（因為for循環(huán)執(zhí)行的順序，只有i大于n時才會停止循環(huán)，所以i=n+1的時候，還會再判斷一下i<=n，所以相比較而言會多執(zhí)行一次）。

00004. i++執(zhí)行n次。

匯總一下，上述代碼執(zhí)行n+1+n+1+n=3n+2次。

如果用極限思維，n->∞，3n+2 ~ 3n ~ n；記作O(n)。O(n)就是上述代碼的時間復(fù)雜度。

● 高級程序員的代碼：

… …

   (1+n)*n/2

… …

如上，同樣的計算1加到n，采用高斯算法就簡單多了。上述代碼只需要執(zhí)行1次，沒有循環(huán)。所以時間復(fù)雜度就是O(1)。

● 小結(jié)

O(1)和O(n)的區(qū)別是什么呢？當(dāng)上述”初級程序員代碼“和”高級程序員代碼”中的變量n不斷增大的時候，高斯算法的時間復(fù)雜度基本不變，還是O(1)。但是“初級程序員代碼”的時間復(fù)雜度就會增加。

對于計算機來說，高斯算法求解1連續(xù)加到n的計算速度遠遠大于for循環(huán)的速度。速度越快，系統(tǒng)的性能就會越好。

到此，相信大家對“怎么理解Java算法復(fù)雜度”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

本文題目：怎么理解Java算法復(fù)雜度-創(chuàng)新互聯(lián)
本文路徑：http://bm7419.com/article2/dihdoc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、靜態(tài)網(wǎng)站、手機網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、軟件開發(fā)、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)