如何去評價一個代碼它的效率高不高呢？ 我們通常從兩個方面去看！

成都創(chuàng)新互聯(lián)是專業(yè)的鄭州網(wǎng)站建設公司，鄭州接單;提供網(wǎng)站建設、成都網(wǎng)站建設,網(wǎng)頁設計,網(wǎng)站設計,建網(wǎng)站,PHP網(wǎng)站建設等專業(yè)做網(wǎng)站服務;采用PHP框架,可快速的進行鄭州網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

• 時間復雜度：主要衡量一個算法的運行速度
• 空間復雜度：主要衡量一個算法所需要的額外空間

1. 時間復雜度 1.1 時間復雜度的定義

在計算機科學中，算法的時間復雜度是一個數(shù)學函數(shù)，它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。

1.2 大O漸進表示法

public class test {void fun(int N){int count = 0;
        for (int i = 0; i< N; i++) {  // 執(zhí)行了 n*n 次
            for (int j = 0; j< N; j++) {count++;
            }
        }
        
        for (int i = 0; i< 2*N; i++) {   // 執(zhí)行 2n 次
            count++;
        }
        
        int N= 10;
        while ((N--)>0){// 執(zhí)行 10 次
            count++;
        }
    }

所以 fun()方法 執(zhí)行的基本次數(shù)為：

??????????????????????????????????????????F（N）= N^2 + 2N + N

在實際中我們計算時間復雜度時，并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，所以我們使用大O（是用于描述函數(shù)漸進行為的數(shù)學符號）的漸進表示法。

1.3 推導大O階方法

• 1、用常數(shù)1取代運行時間中的所有加法常數(shù)
• 2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項
• 3、如果最高階項存在且不是1，則去除最高階項的系數(shù)。得到的結果就是大O階。
  使用大O的漸進表示法以后，func1的時間復雜度為： O(N^2)
  
  通過以上我們可以看出 大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示了執(zhí)行次數(shù)。

1.4 時間復雜度存在三種情況

• 最壞情況：任意輸入規(guī)模的大運行次數(shù)（上界）
• 平均情況：任意輸入規(guī)模的期望運行次數(shù)
• 最好情況：任意輸入規(guī)模的最小運行次數(shù)（下界）

舉個最簡單的例子：在一個長度為N的數(shù)組中查找一個x
最好情況：1次找到，在開頭
最壞情況：N次找到，在末尾
平均情況：N/2次找到，（1+2+3+…N）/ N = N/2 + 1/2 =>N/2 （每個數(shù)據(jù)要找的次數(shù)/數(shù)組的長度)

一般在沒有特殊情況的說明下，都是指最壞時間復雜度。

1.5 幾個常見的求時間復雜度的例子

實例1：

// 計算折半查找的時間復雜度
    int binarySearch(int[] array, int value) {int left= 0;
        int right = array.length - 1;
        while (left<= right ) {int mid = left + ((right - left ) / 2);
            if (array[mid]< value)
                left = mid + 1;
            else if (array[mid] >value)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }

最好情況下：O(1) ；最差情況下：O(logN).

---

實例二：

// 計算遞歸求階層的時間復雜度
long factorial(int N){return N< 2 ? N : factorial(N - 1) * N;
}

遞歸的時間復雜度：遞歸次數(shù) * 每次遞歸后代碼的執(zhí)行次數(shù)

所以 遞歸次數(shù) * 每次遞歸后代碼的執(zhí)行次數(shù) = 3 * 1 = 3 ---------- 遞歸次數(shù) N * 1 = N

2. 空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 ?？臻g復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)?？臻g復雜度計算規(guī)則基本跟時間復雜度類似，也使用大O漸進表示法。

例1：

void bubbleSort(int[] array) {for (int end = array.length; end >0; end--) {boolean sorted = true;
            for (int i = 1; i< end; i++) {if (array[i - 1] >array[i]) {Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {break;
            }
        }
    }

在上述代碼中 boolean sorted = true 就是臨時使用的常數(shù)個額外空間，所以空間復雜度為O(1)。
又因為此算法執(zhí)行時所需的輔助空間相對于輸入數(shù)據(jù)而言是個常數(shù)，則稱此算法為原地工作，空間復雜度為O(1).

---

例二：

long[] fibonacci(int n) {long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i<= n; i++) {fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }
        return fibArray;
    }

可以看出 隨著 n 越來越大，數(shù)組也越來越大，所以空間復雜度為O(N)。

3. 常見的時間復雜度所耗時間的大小排列

0(1)< O(logN)< O(N)< O(nlogN)< O(N^2)< O(N ^3)< O(2 ^N)< O(N!)< O(N ^N)

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：數(shù)據(jù)結構之【時間復雜度和空間復雜度】-創(chuàng)新互聯(lián)
文章源于：http://weahome.cn/article/ccopgj.html