下面就首先從一些數學問題入手。

Q1：?如何證明時間復雜度O(logN) < O(N) < O(NlogN) < O(N2) <?O(2N) < O(N!) < O(NN)?

A：?如果一個以整數為參數的不等式不能很容易看出不等的關系，那么最好用圖示或者數學歸納法。

很顯然，使用圖示的方法也不能很好得到上面的關系圖，因為圖示范圍較小，不能證明當N趨于無窮大依然成立。所以，數學歸納法成為首選。

不失一般性，假設logN的底數為2：

欲證明O(logN) < O(N)，只需要證明log2N < N = log22N, 只需要證明N <?2N ?

當N = 1時成立，假設上面成立，現在只要證明N + 1 < ?2N+1 ? ??

這個顯然成立。

O(N) < O(NlogN)?很容易證明，這里不再證明；

由O(logN) < O(N)，?很容易證明 O(NlogN) < O(N2)

對于O(N2) <?O(2N) < O(N!) < O(NN)，由上面的方法同樣很容易證明，這里不再贅述。

Q2：如何證明1+2+.....+n = n(n+1)/2?? ?

A： 對于以整數n為變量的表達式的證明方式當然是數學歸納法。

當n=1時，很顯然成立；假設等于n的時候也成立，下面就要證明當等于n+1的時候依然成立。

1+2+...+n+(n+1) = n(n+1)/2+(n+1)=(n+1)(n+2)/2.顯然成立。所以證明此等式成立。

當然，證明這個還可以用高斯的NB計算方法：

假設S=1+2+...+(n-1)+n

同樣S=n+(n-1)+...+2+1

所以兩式相加： 2S=(n+1)+(n+1)+...+(n+1)+(n+1)=n(n+1);

所以S=n(n+1)/2.

當然，還有另外一種畫圖的方式來證明：

?如上圖，在一個邊長為n的正方形里面，存放了1,2,...n這些小圓圈。

可以看出，(1+2+...+n)*2=n*n+n;

所以1+2+...+n=n(n+1)/2.

---

微風不燥，陽光正好，你就像風一樣經過這里，愿你停留的片刻溫暖舒心。

我是程序員小迷（致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等編程技術的技巧經驗分享），若作品對您有幫助，請關注、分享、點贊、收藏、在看、喜歡，您的支持是我們為您提供幫助的最大動力。

歡迎關注。助您在編程路上越走越好！