算法入門課程（1）時間複雜度入門

· · 算法·理论

前言

這個 Part 可能略微枯燥，但是對於 OI 學習來說是非常必要的。

引入

算法競賽中我們希望在規定的空間和時間中解決問題，然而我們需要一個工具來刻劃程序的效率。

上機測試

我們造一組數據，然後評測，看看程序完成任務需要的時間，時間越快越代表算法優秀。

優點是直觀，易於比較，說服力強。

但是，存在以下問題：

計算操作次數

上述測試顯然是不夠科學的，事實上，我們通常可以直接把程序的操作次數表示出來，來刻劃算法的執行時間。

for(int i=1;i<=n;i++)
{
    for(int j=i+1;j<=n;j++)
    {
        cout<<i<<' '<<j<<endl;
    }
}

上面的代碼枚舉了所有的整數二元組 (i,j) 滿足 i,j\in[1,n],i\not=j，那麼我們枚舉的數量應該為 \binom{n}{2} ,因此我們得到枚舉的數量應該為 \binom{n}{2} 。

這個辦法看起來科學多了，但是還是不夠好，因為當我們的代碼足夠長的時候，操作次數的形式會很冗雜，導致無法直觀地看出代碼大致的效率。舉個例子：

cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=0,x;j<m;j++)
{
    cin>>x;
    A[i]|=(1^x)<<j;
}
F[0][0]=1;
for(int i=0;i<(1<<m);i++)
{
    int t=0;
    for(int j=1;j<m;j++)t|=(i>>j&1)&(i>>(j-1)&1);
    if(!t)V.push_back(i);
}
for(int i=1;i<=n;i++)
for(int S:V)
{
    if(S&A[i])continue;
    for(int S2:V)
    {
        if(S&S2)continue;
        (F[i][S]+=F[i-1][S2])%=Mod;
    }
}
int Ans=0;
for(int i:V)(Ans+=F[n][i])%=Mod;
cout<<Ans<<endl;

以上是我在某個問題中給出的解答，我們可以表示出操作次數最壞情況下為 nm+(m-1)2^m+n4^m+2^m，這個式子真讓人感到頭大！我們很難對於這個式子進行理解與評估。

事實上，我們往往關心的是算法速度的規模而不是一個很精確的多項式，所以我們能否直接表示出算法的規模呢？

時間複雜度

這時就可以引入時間複雜度來描述算法效率的規模。

在電腦科學中，演算法的時間複雜度（time complexity）是一個函數，它定性描述該演算法的執行時間。這是一個代表演算法輸入值的字串的長度的函數。時間複雜度常用大O符號表述，不包括這個函數的低階項和首項係數。

——Wikipedia

注意：如果不能省略其他的未知數，比如 \mathcal O(nm) 這個形式是正確的。

這樣刻劃是很直觀的，比如上面第一個的問題，我們枚舉的數量應該為 \binom{n}{2} ，如果我們可以整理為 \mathcal O(n^2) 的形式，就易於理解了。

第二個問題，我們可以直接整理為 \mathcal O(n4^m)，這比原來的形式簡潔多了！

常見的時間複雜度：

在之後的課程中我們會經常遇到這些複雜度，如果你沒有聽懂我說的是什麼時間複雜度，請立刻指出來。

常數

習慣上算法競賽喜歡把時間複雜度省去的“低階項和首項係數”部分所帶來的效率差異稱為常數差異，比如你可能會聽到“常數大”或者“常數小”這樣的說法。

常數其實也是很重要的，有的時候，一個優秀的常數會導致一個時間複雜度不優秀的算法通過題目，一個常數很大的代碼也可能無法通過題目。

減小常數的一個口語化表述叫做“卡常”。

減小常數的技巧是有很多的，此處就不詳細介紹，這是需要在長期的實踐中了解的，“實踐是檢驗真理的唯一標準”。

平均時間複雜度

這裡涉及到了一些期望的概念，可能有點超綱。

Bogo排序 是個非常低效率的排序演算法，通常用在教學或測試。其原理等同將一堆卡片拋起，落在桌上後檢查卡片是否已整齊排列好，若非就再拋一次。

——Wikipedia

我們發現：

最好情況下，排序一次就能解決，這叫做最佳時間複雜度 \mathcal O(n)。

最壞情況下，排序可能需要無限的時間完成，這叫做最劣時間複雜度 \mathcal O(\infty)。

我們發現，最佳時間複雜度和最劣時間複雜度都太過於極端，不利於我們描述速度，所以我們通常要考慮平均時間複雜度。

平均時間複雜度是在期望情況下的時間複雜度，如果你不知道什麼是期望，你可以先忽視以下的內容。

我們發現每次有 \dfrac 1{n!} 的概率隨機到正確的排序，所以我們期望在 n! 次隨機之後完成排序，因此我們認為平均時間複雜度為 \mathcal O(n·n!)。

當算法的時間複雜度有隨機因素在，那麼我們通常考慮平均時間複雜度，否則我們通常討論最劣時間複雜度。

習題

1.如果我們枚舉了一個整數三元組 (i,j,k)，均在 [1,n] 內並且兩兩不相同，那麼時間複雜度是？

2.如果我們對於所有的整數 x\in [1,n] 都枚舉其倍數 y\in[1,n],x|y，那麼時間複雜度是？

3.如果我們對於所有的2 的整數次冪 2^t\in [1,n],t\in\mathbb{N} 都枚舉其倍數 y\in[1,n],2^t|y，那麼時間複雜度是？

4.如果你學習過快速排序，請問每次我選擇當前區間的最左端數字作為基准數，這樣時間複雜度是正確的嗎？我應該如何改正？