怎么理解Java算法復雜度

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

大O符號

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

2.1、數學舉例：

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

00002. 當x趨于無窮大的時候，記作x—>∞。

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

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

當x=5的時候：

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

2x^2=50.

當x=500的時候：

2x^2+2x+2=501002

2x^2=250000.

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

通過極限的思想，我們將函數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是用來刻畫被截斷的無窮級數尤其是漸近級數的剩余項。大O符號表示函數的漸進性上界。就好比上面的數學舉例，函數f(x)=2x^2+2x+2 漸進級數的剩余項就是x^2，記作O(x^2)。也就是說O(x^2)是f(x)的漸進性上界。

時間復雜度

題目：求1+2+3+……+n的和。（高斯算法）

● 初級程序員的代碼：

… …

    for (int i = 1; i <= n; i++) {

        sum+=i;

    }

… …

分析：

00001. 上述代碼中的sum+=1執行多少次？ 答案：n次。

00002. int i=1執行1次。

00003. i<=n執行n+1次。（因為for循環執行的順序，只有i大于n時才會停止循環，所以i=n+1的時候，還會再判斷一下i<=n，所以相比較而言會多執行一次）。

00004. i++執行n次。

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

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

● 高級程序員的代碼：

… …

   (1+n)*n/2

… …

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

● 小結

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

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

到此，相信大家對“怎么理解Java算法復雜度”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！