章節1-1.什麼是演算法與時間複雜度

什麼是演算法

在學會C++的基礎語法後，接下來要進一步了解演算法，首先就是要知道何謂演算法。

若在網路上搜尋「演算法定義」等關鍵字，其實會得到有些抽象的文字。

但其實用直白的話講，演算法其實很像是數學，學習演算法的過程，其實就像是學習如何利用程式，將解決一個數學問題的步驟寫下來，並讓電腦可以執行，然後電腦就可以依據程式，針對這個題目給定的輸入進行運算，得到題目所要求的輸出。
當然這個說法還是粗略的，實際上演算法可以解決的問題不僅涵蓋了數學，更有許多不同的領域。

時間複雜度

演算法的時間複雜度是用來描述一個演算法或者一個程式，執行所需時間與輸入規模之間的關係。
簡單來說，時間複雜度告訴我們隨著輸入數值、數量增大，演算法、程式的執行時間會如何變化。

時間複雜度能幫助我們比較不同演算法的效率。我們希望選擇那些在輸入規模增大時，執行時間增加較慢的演算法。

計算時間複雜度時，我們通常會考慮輸入的變數如何影響計算次數，如輸入「一個整數n，與n個整數a₁,a₂,...,a_n」，要求這n個數的和，基本上只能設一個變數紀錄總和，然後執行n次加法，花費n次計算，此時會將此過程的時間複雜度記作O(n)，讀作「歐n」(總之就是會將複雜度寫成名為O的函數，並讀成歐並將括號內的東西唸出來就好)。

除此之外，假設以上例子變成求給定n個數的和與積，那麼同時會需要進行n次乘法，總運算次數為2n，儘管如此，我們仍將複雜度視為O(n)，因為複雜度關注的是「運算時間隨輸入規模的增長速度」，不論是以上哪個例子，在n翻倍時，運算次數、花費的運算時間都是翻倍而已，因此記為O(n)就好。
簡單來說，計算複雜度時若「運算次數」有係數，可以將係數消去、保留每項的量級就好。

而常見的時間複雜度如下。

O(n)又稱線性時間：執行時間隨輸入之n成正比。例如，輸出n個數中的最大值。

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int max_value=0;//假設此例題的a_i皆為正整數，故將初始最大值設為0，保證後續所有值皆大於此值
    for(int i=0;i<n;i++){
        if(a[i]>max_value)max_value=a[i];
    }
    cout<<max_value;
}

O(n²)又稱平方時間：執行時間隨輸入之n的平方成長。例如，輸出n乘n的乘法表。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<i*j<<' ';
        }
        cout<<'\n';
    }
}

O(1)又稱常數時間：執行時間不隨輸入之變數變化。例如，輸出給定數字的平方。

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
    int n;
    cin>>n;
    cout<<n*n;
}

O(log n)又稱對數時間：執行時間隨輸入之n的對數成長。例如，二分搜尋，在2-1介紹。

O(n log n)又稱線性對數時間：例如，高效的排序演算法如快速排序、合併排序等，在2-2介紹。

此外當然還有其他的時間複雜度，可以參考維基百科，另外其中也有「不同時間複雜度對n的變化趨勢」，可以簡單看過以增強對時間複雜度的理解。

至於複雜度的計算，除了上述直接估算運算次數的方法外，還有三個要點可以注意。

第一個，不同程式片段並排時，複雜度相加，如以下程式總時間複雜度為O(n+m)，由於不知道n、m兩者的關係，因此需保留n、m兩者，這代表假設n極大時，主要運算時間受n影響，反之亦然，也可能n、m量級相同。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        //O(1)的運算
    }
    //此時以上迴圈總時間複雜度為O(n)
    for(int i=0;i<m;i++){
        //O(1)的運算
    }
    //此時以上迴圈總時間複雜度為O(m)
}

第二個，若是以迴圈包覆時，累加每次迴圈的運算次數，部份情況下亦可直接相乘。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            //O(1)的運算
        }
    }
    //以上迴圈很顯然單看內層的時間複雜度是O(m)，然後因外層迴圈會執行n次，總運算次數為n*m，因此總時間複雜度為O(nm)
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            //O(1)的運算
        }
    }
    //以上迴圈較複雜，從i=0到i=n-1，內層迴圈的運算次數依序為n次、n-1次、...、1次，可以算出總運算次數為n^2/2+n/2
    //捨棄掉較小的項並消除係數後，得到複雜度為O(n^2)，由此可知若內層同樣為近似線性複雜度，則可以直接相乘
}

第三點，若運算以函式包起來，仍要將該複雜度帶入運算。如以下程式使用C++內建函示gcd(a,b)，可以算出兩個整數a,b的最大公因數，若k值等於a,b中較大的值，則單次計算複雜度為O(log k)，而多個數字的最大公因數可以用以下程式得到。
此程式將O(log k)的函式執行n次，總複雜度為O(n log k)，其中k為輸入的數列中的最大值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a,ans;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        if(i==0)ans=a;//第一個數直接紀錄為最大公因數
        else ans=gcd(ans,a);//第二個數開始將目前記錄的最大公因數與當前數字取最大公因數，再紀錄為新的最大公因數
    }
}

在知道如何計算複雜度後，回到最早計算複雜度的目的，就是為了衡量程式的執行時間。
這裡提供一個快速的判別方式，將題目中各變數的最大值帶入計算，也就是考慮最極端的情況下，得到的結果是預估計算次數。如複雜度為O(nm)，而n、m的最大值皆為10⁴，則最壞情況下的計算次數約為10⁴*10⁴=10⁸。
而電腦的計算速度通常可以以保守每秒10⁸次計算，因此以上的例子正常來講在1秒內能執行完。

但以上的計算方法也相當簡略，實際情況仍要視許多因素而定，如電腦的計算速度在某些簡單的如加減法的運算下，可以達到每秒10⁹次以上，另外由於我們在計算複雜度時會省略係數，因此實際的計算次數可能被高估或低估，若能還原較接近實際的運算次數能確保估計執行時間誤差比較小。
總而言之每秒10⁸的運算次數是相當保守的，假設題目的時間限制為3秒，那麼帶入複雜度後只要在3*10⁸或是在同一個數量級內都是有機會通過的。

稍微提及一下，除了時間複雜度外，也有評估演算法過程中使用記憶體大小的空間複雜度，但由於必須評估空間複雜度的題目較少，因此筆者後續若提到「複雜度」皆指時間複雜度。