作者 | OverRedMaple

來源 | CSDN 博客

封圖 | CSDN付費下載於東方 IC

如果你還在發愁究竟怎麼計算時間複雜度和空間複雜度，那你是來對地方了！

名詞解釋：

在計算機科學中，時間複雜性，又稱時間複雜度，算法的時間複雜度是一個函數，它定性描述該算法的運行時間。這是一個代表算法輸入值的字符串的長度的函數。時間複雜度常用大O符號表述，不包括這個函數的低階項和首項係數。使用這種方式時，時間複雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。

時間複雜度的表示方法

其實就是算法（代碼）的執行效率，算法代碼的執行時間。我們來看下面一個簡單的代碼：

<code>int sumFunc(int n) {/<code><code> int num = 0; // 執行一次/<code><code> for (int i = 1; i <= n; ++i) { // 執行n次/<code><code> num = num + i; // 執行n次/<code><code> } /<code><code> return num;/<code><code>}/<code>

假設，每行代碼的執行時間為t，那麼這塊代碼的時間就是(2n+2)*t

由此得出：代碼執行時間T(n)與代碼的執行次數是成正比的！

那麼我們來看下一個例子：

<code>int sumFunc(int n) {/<code><code> int num = 0; // 執行一次/<code><code> for (int i = 1; i <= n; ++i) { // 執行n次/<code><code> for (int j = 1; j <= n; ++j) { //執行n*n次/<code><code> num = num + i * j; // 執行n*n次/<code><code> }/<code><code> }/<code><code>}/<code>

同理，該代碼執行時間為(2n*n+n+1)*t，沒意見吧？繼續往後看！

注意：在數據結構/算法中，通常使用T(n)表示代碼執行時間，n表示數據規模大小，f(n)表示代碼執行次數綜合，所以上面這個例子可以表示為f(n)=(2n*n+n+1)*t，其實就是一個求總和的式子，O

根據上面兩個例子得出結論：代碼的執行時間 T(n)與每行代碼的執行次數 n 成正比，人們把這個規律總結成這麼一個公式： T(n) = O(f(n))

所以呢，第一個例子中的 T(n)=O(2n+1)，第二個例子中的 T(n)=O(2n*n+n+1)，這就是時間複雜度表示法，也叫大O時間複雜度表示法。

但是，大O時間複雜度並不具體表示代碼真正的執行時間，而是表示代碼執行時間隨數據規模增長的變化趨勢，所以，也叫作漸進時間複雜度，簡稱時間複雜度。

與泰勒公式相反的是，算了，扯哪去了…

當n變得越來越大時，公式中的低階，常量，係數三部分影響不了其增長趨勢，所以可以直接忽略他們，只記錄一個最大的量級就可以了，所以上述兩個例子實際他們的時間複雜度應該記為：T(n)=O(n) ，T(n)=O(n*n)

我想你應該明白大致是怎麼回事了，那麼我們來看看如何去計算它？

時間複雜度的分析與計算方法

（1）循環次數最多原則

我們上面說過了，當n變得越來越大時，公式中的低階，常量，係數三部分影響不了其增長趨勢，可以直接忽略他們，只記錄一個最大的量級就可以了。因此我們在計算時間複雜度時，

<code>int sumFunc(int n) {/<code><code> int sum = 0; //執行1次，忽略不計/<code><code> for (int i = 0; i < n; i++) {/<code><code> sum += i; // 循環內執行次數最多，執行次數為n次，因此時間複雜度記為O(n)/<code><code> } /<code><code> return sum; //執行1次，忽略不計/<code><code>}/<code>

（2）加法原則

<code>int sumFunc(int n) {/<code><code> int sum = 0; //常量級，忽略/<code><code> for (int i = 0; i < 99; i++) {/<code><code> sum += i; //執行100次，還是常量級，忽略/<code><code> }/<code>
<code> for (int i = 0; i < n; i++) {/<code><code> sum += i; //執行n次/<code><code> }/<code>
<code> for (int i = 0; i < n; i++){/<code><code> for (int j = 0; j < n; j++) {/<code><code> sum += i; //執行n*n次/<code><code> }/<code><code> }/<code><code> return sum;/<code><code>}/<code>

上述例子中，最大的兩塊代碼時間複雜度分別為 O(n)和O(n*n)，其結果本應該是：T(n)=O(n)+O(n*n)，我們取其中最大的量級，因此整段代碼的複雜度為：O(n * n)

所以得出結論：量級最大的那段代碼時間複雜度=總的時間複雜度

（3）乘法原則

嵌套代碼的複雜度等於嵌套內外代碼複雜度的乘積

<code>void Func1(int n) {/<code><code> for (int i = 0; i < n; i++) {/<code><code> Func2(n); //執行n次，每次都會調用Func2函數執行n次/<code><code> }/<code><code>}/<code><code>void Func2(int n) {/<code><code> int sum = 0;/<code><code> for (int i = 0; i < n; i++)/<code><code> {/<code><code> sum += 1; //執行n次/<code><code> }/<code><code>}/<code>

因此這段代碼時間複雜度為O(n) * O(n) = O(n*n) = O(n*n)

同理，如果將其中一個n換成m，那麼它的時間複雜度就是O(n*m)

常見的幾種時間複雜度

（1）O(1)常量級時間複雜度

<code>void Func(void) {/<code><code> for (int i = 0; i < 100; i++) {/<code><code> printf("hello"); //執行一百次，也是常量級，記為O(1)/<code><code> }/<code><code>}/<code>

<code>void Func(void) {/<code><code> printf("hello");/<code><code> printf("hello"); /<code><code> printf("hello");/<code><code> //各執行一次，還是記為O(1)/<code><code>}/<code>

相信你也看明白了，O(1)不是說代碼只有一行，這個1它代表的是一個常量，即使它有以前一萬行這樣的也是O(1)，因為它是固定的不會變化（也就是常量），

（2）常見的O(n)複雜度

<code>void Func(int n) {/<code><code> for (int i = 0; i < n; i++) {/<code><code> printf("hello");/<code><code> }/<code><code>}/<code>

不用多說了吧！繼續！

（3）O(logn)，O(nlogn) ，這就有點難度了！

首先我們來回憶以下換底公式：

記住公式啊，來看例子：

<code>void Func(int n) {/<code><code> for (int i = 1; i < n; i++) {/<code><code> i = i * 2;/<code><code> }/<code><code>}/<code>

可以看出，i = i * 2這行代碼執行次數是最多的，那麼到底執行了多少次呢？

第一次 i=2，執行第二次 i=4，執行第三次 i=8…

假設它執行了x次，那麼x的取值為：

當上述代碼的2改成3的時候，x的取值也就是：

當然不管log的底數是幾，是e也好，是10也罷，統統記為：

這是為啥子念？由換底公式可以計算出：

換底之後，可以看出log3(2)其實就是一個常數，忽略它！而在這場遊戲中，log默認就是以2為底的，所以統統記為O(logn)。

<code>void Func(int n) {/<code><code> for (int i = 0; i < n; i++) {/<code><code> Func2(n); //執行n次，嵌套調用，每次調用執行logn次/<code><code> }/<code><code>}/<code><code>void Func2(int n) {/<code><code> for (int i = 0; i < n; i++)/<code><code> {/<code><code> i = i * 2; //執行logn次/<code><code> }/<code><code>}/<code>

所以這個O(nlogn)也很好理解了吧！

閱讀更多 CSDN 的文章

關鍵字: 數據結構 計算方法 CSDN