【算法】懂點算法（一）— 算法的時間空間復雜度
寫在前面
大廠秋招提前批已經開啟，吹響了應屆生秋招的號角，也就意味著大家要加入殘酷的招聘競爭。筆試面試是規范求職過去的坎，而算法對于大多數人而言是是道難關，只有通過系統學習和理解刷題才能征服它。
為了幫助更多人去理解數據結構和算法，將開辟新的博文系列《懂點算法》，希望大家能夠渡過痛苦的日子。本人在算法研究上，能力有限，希望大家能夠取其精華，汲取干貨。
什么是算法
算法(Algorithm)是指用來操作數據、解決程序問題的一組方法。
衡量不同算法之間的優劣有兩種方法：
- 事后統計法：通過統計、監控，利用計算機計時器對不同算法的運行時間進行比較，從而確定算法效率的高低，但是具有非常大的局限性。
- 事前分析估算法：在計算機程序編制前，依據統計方法對算法進行估算。
舉個栗子，我們知道斐波那契數列的規律是：數列從第3項開始，每一項數值是前兩項數值之和。即：0,1,1,2,3,5,8...
分析：我們觀察斐波那契數列的規律，可以看到數列在使用算法進行表示的時候，需要分為兩種情況，即前兩項，和第三項開始后的元素的計算。
最簡單的方法是使用遞歸進行實現斐波那契數列的算法：
- function fib(num){
- if(num <= 1) return num;
- return fib(num - 1) + fib(num - 2);
- }
當然，也可以使用循環方法進行實現：
- function fib(num){
- if(num <= 1) return num;
- let num1 = 0, num2 = 1;
- for(let i = 0; i < num - 1; i++){
- // 每次加都是前兩項之和
- let sum = num1 + num2;
- // 相加之前num2要作為下一次相加的num1
- num1 = num2;
- // 相加的結果要作為下一個num2
- num2 = sum;
- // 但是呢，上面兩句代碼不可交換哦
- }
- return num2;
- }
其實，高級程序語言編寫的程序在計算機上運行的消耗時間取決于以下因素：
- 算法采用的策略、方法(算法的好壞)
- 編譯產生的代碼質量(軟件性能)
- 問題的輸入規模(輸入量的多少)
- 機器執行指令的速度(硬件性能)
總的來說，程序的運行時間主要取決于算法的好壞和問題的輸入規模。
時間復雜度和空間復雜度
我們都學過高斯的故事，主要內容是這樣的：在高斯上學時老師提問如何計算100以內非0自然數的和，即計算1+2+……+99+100=? 當時很多同學都在從頭加到尾計算，但是高斯并沒有忙著去計算，而是思考問題。
經過高斯觀察后發現，第一項與最后一項的和等于第二項與倒數第二項的和一樣，都是101，同時他發現其他項也符合這樣的規律。而總共有50對，所以結果就是101×50=5050。于是，他成為班里第一個計算出答案的人。
告訴我們道理：磨刀不誤砍柴工，用對方法更輕松。
那么，我們仔細分析下高斯算法和常規算法的優劣。
常規算法：
- function commonFunc(){
- let sum = 0; //執行一次
- for(let i = 1; i <= 100; i++){ //執行n+1次
- sum += i;//執行n次
- }
- return sum;//執行1次
- }
高斯算法：
- function guassFunc(){
- let sum = 0;//執行1次
- sum = (1 * ｎ) ＊ ｎ／２；//執行1次
- return sum;//執行1次
- }
如上所示，常規算法的執行次數是2n+3次，而高斯算法的執行次數是3次。由于首尾語句的執行次數是相同，主要關注中間算法部分則是n次與1次的區別，很顯然高斯算法遠優于常規算法。
算法時間復雜度
我們看下《大話數據結構》中是如何定義算法時間復雜度的。
算法時間復雜度：在進行算法分析時，語句總的執行次數T(n)是關于問題規模n的函數，進而分析得到T(n)隨n的變化情況并確定T(n)的數量級。算法的時間復雜度，就是算法的時間量度，記作：T(n)=O(f(n))。它表示隨時間規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。
我給你翻譯翻譯，就是說時間復雜度是用于估算程序運行時間的量度。假設算法的問題規模為n，那么操作單元數量(用于表示程序消耗的時間)，隨著數據規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作時間復雜度O(f(n))。
T(n)=O(f(n))
- T(n)表示代碼執行的時間
- n表示數據規模的大小
- f(n)表示每行代碼執行的次數總和
- O表示代碼執行時間T(n)與T(n)成正比
我們看到上面描述中提到了O()來體現算法時間復雜度，也被稱為大O計法。大O用于表示上界，即用于表示算法最壞情況下運行時間的上界，也就是在最壞情況下運行所花費的時間。
推導大O階方法：
- 用常數1取代運行時間中的所有加法常數
- 在修改后的運行函數次數中，只保留最高階項
- 如果最高階項存在且不是1，則去除與這個項相乘的常數
接著，我們自己動手練習下算法時間復雜度的計算方法，如下：
- function testFunc(n){
- for(let i = 0; i < n; i += i){ //執行1+log2(n)次
- for(let j = 0; j < n; j++){ //執行n+1次
- console.log("yichuan");//執行(1+log2(n))*(n+1)次
- }
- }
- }
我們看到，在第一次for循環中，i+=i即i=i+i=2i，那么當2i=n時得到n=log2(n)，要跳出循環即要執行1+log2(n)次語句。而在第二次for循環中語句要執行n+1次才能跳出循環，而打印語句的執行次數是(1+log2(n))*(n+1)次。其實采用大O記數法忽略加法常數和最高次項系數，那么得到就是執行nlogn次，記作O(nlogn)。
記住，在計算算法時間復雜度時，可以根據高階次數的實際情況忽略其加法常數和最高次項系數、對數項的底數。
常見的計數階數有：
我們可以看到常見的算法時間復雜度計算階數所耗費時間的比較：
各種時間復雜度曲線如下：
算法空間復雜度
其實，在代碼時完全是犧牲空間來換取時間。類比于算法時間復雜度，空間復雜度表示算法存儲空間與數據規模之間的增長關系。
算法空間復雜度：通過計算算法所需的存儲空間實現，而計算公式是：S(n)=O(f(n))。
- n表示問題的規模
- f(n)表示語句中關于n所占存儲空間的函數
- function spaceFunc(n){
- const arr = [];//第2行代碼
- arr.length = n;//第3行代碼
- for(let i = 0; i < n; i++){
- arr[i] = i * i;
- }
- for(let j = n - 1; j >= 0; --j){
- console.log(arr[i]);
- }
- }
觀察上述代碼可得：在第2行代碼中，在內存開辟一塊空間存儲變量arr并對其賦值空數組;在第3行代碼中，將數組的長度設置為n，數組中會自動填充n個undefined;此外剩下代碼并未占據更多空間，因此整段代碼的空間復雜度為O(n)。
最壞情況和平均情況
最壞情況運行時間是這段程序在運行所耗費時間最多的情況，沒有比這更糟糕的情況。通常，我們提到的運行時間指的都是最壞情況的運行時間。
平均情況運行時間所指的是程序所期望的平均時間，但是在實際測試中，很難通過分析得到，需要通過一定數量的實驗數據和估算。
我們知道，在進行查找n個隨機數中查找某個數字，最好的情況是查找第1個數字就找到，此時的時間復雜度是O(1)，而最壞的情況下是查找到第n個數字才找到。那么，在查找數字的算法中最壞情況的時間復雜度是O(n)，平均情況的時間復雜度是O((1+n)/2)即O(n/2)。
小結
在本文中，筆者介紹了什么是算法、為什么要用算法、如何衡量算法的時間復雜度和空間復雜度以及算法的最壞情況和平均情況的概念。
