Day 7 不數迴圈就沒辦法分析了？技豈是如此不便之物其一

2023 iThome 鐵人賽

DAY 7

自我挑戰組

CS補完計畫—演算法與資料結構的第三次衝擊系列第 7 篇

15th鐵人賽資料結構與演算法廢文貓咪複雜度

暗魂駭客

團隊每件事都壓死線的大家真的可以完賽嗎？

2023-09-22 21:37:04

275 瀏覽

分享至

接下來幾篇要介紹時間複雜度各種的分析技巧，不過因為個人能力有限，因此這裡開始會大量參考網路資源，尤其是 AA 競程在 YouTube 的時間複雜度教學影片。

AA 競程是個非常專業的競技程式補習班，他們的學生很多都在 APCS、TOI、資訊能力競賽等等都拿到了極佳的成果。最近AA 競程的 YouTube 有在做 Atcoder Beginner Contest 的賽後講題，有興趣的人可以去參考看看。

不過當然我雖然參考影片寫，不過我不會止步於影片本身。我會盡量把裡面留作練習卻沒那麼好想和我自己學習時曾經卡住的點完整講過一遍。

那麼就讓我們開始接下來的內容！

數迴圈

昨天提到過其實只要取被執行最多次的指令們，把它們的漸進複雜度相加就可以了。

此時有一個用的小觀察：迴圈套越多層內部被執行的次數越多，所以只要從外往內數迴圈執行次數的漸進複雜度後加總再取一次漸進複雜度就可以了。

那這種技巧之所以會叫做數迴圈，是因為要知道內層迴圈的執行次數，其實只要從外層一路「乘」進來就好了，過程就好像在「數」有幾層迴圈一樣。

int func(int n, int m) {
    int result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            ++result;
        }
        for (int j = 0; j < n; ++j) {
            ++result;
        }
    }
    for (int i = 0; i < m; ++i) {
        ++result;
    }
    return result;
}

以上面程式為例：最深的迴圈出現在三個 ++result 那邊，而它們的漸進複雜度相加是： $\mathcal{O}{(n\cdot m)}+\mathcal{O}{(n^2)}+\mathcal{O}{(m)}=\mathcal{O}{(n\cdot m+n^2)}$

值得注意的是，因為無法確定 $n$ 和 $m$ 誰大誰小，因此不能把 $n\cdot m$ 消去。

數學分析

剛剛提到的數迴圈，雖然是最常用的技巧，但也是新手最容易搞錯和誤用的技巧。

一個迴圈就是 $O(n)$
兩個迴圈就是 $O(n^2)$

可能有些初學者學過剛剛的數迴圈後，會得出上面這種結論，但事情並非總是這麼簡單！

有時候迴圈不會像上面的例子那樣執行次數穩定、每次次數都固定，這時候我們就需要做一點數學分析來確定它的上界是什麼，以估算它的漸進複雜度。

這邊以 Atcoder 的 ARC133 A - ABC 舉例

題意

給定正整數 $K$ ，求有幾個正整數三元組 $(A, B, C)$ 能滿足 $ABC\le K$ 。若兩個三元組數字完全相同但排列不一樣也會被分開計為不同的三元組。

$1\le K\le 2\times 10^5$
時間限制 2 秒

超暴力 $\mathcal{O}{(K^3)}$

首先可以用最直覺最暴力的方式來想該怎麼做：執行試遍 A、B、C 所有可能的數字！

因此我們可以像下面這樣三層迴圈暴力枚舉：

void solve() {
    int K;
    cin >> K;
    long long ans = 0;
    for (int A = 1; A <= K; ++A) {
        for (int B = 1; B <= K; ++B) {
            for (int C = 1; C <= K; ++C) {
                if ((long long)A * B * C <= K) {
                    ++ans;
                }
            }
        }
    }
    cout << ans << "\n";
}

這看起來真是暴力至極，時間複雜度是 $\mathcal{O}{(K^3)}$ ，看看輸入 $K$ 的最大數值 $2\times 10^5$ ， $K^3=8\times 10^{15}$ ，回想 Day 4 的實測，絕對不可能在兩秒內跑完。

還是很暴力 $\mathcal{O}{(K^2)}$

但真的有必要枚舉那麼多種可能嗎？看看我們的條件判斷，當我們已經知道 $A$ 、 $B$ 的情況下能否直接判斷出 $C$ 的數量？

假設 $A$ 、 $B$ 已知，此時不等式 $https://chart.googleapis.com/chart?cht=tx&chl=ABC%5Cle%20K%5CRightarrow%20C%5Cle%5Cfrac%7BK%7D%7BAB%7D$ 且因為 $C$ 為正整數，所以 $https://chart.googleapis.com/chart?cht=tx&chl=1%5Cle%20C%5Cle%5Cfrac%7BK%7D%7BAB%7D$ 。

既然都知道符合需求的 $C$ 的範圍是 $https://chart.googleapis.com/chart?cht=tx&chl=%5B1%2C%20%5Cfrac%7BK%7D%7BAB%7D%5D$ ，就不用大費周章的枚舉了：

void solve() {
    int K;
    cin >> K;
    long long ans = 0;
    for (int A = 1; A <= K; ++A) {
        for (int B = 1; B <= K; ++B) {
            // 區間右界減去左界再加一
            ans += (K / A / B) - 1 + 1;
        }
    }
    cout << ans << "\n";
}

如此一來時間複雜度降至 $\mathcal{O}{(K^2)}$ ，不過 $(2\times 10^5)^2=4\times 10^{10}$ 　，當初我們 Day 4 的結論是一般的電腦每秒的步驟數約落在 $10^8\sim 10^9$ ，目前要在兩秒內跑完還是沒辦法，因此得必須繼續優化。

不明所以的暴力 $\mathcal{O}{(???)}$

我們再想想，我們在枚舉 $B$ 的過程中，真的每次都能產生出符合需求的 $C$ 嗎？

例如像 $A=K$ ，則 $B$ 不可能大於 1！所以 $B$ 從 1 之後的枚舉都是無效的，事實上 B 最大只能到 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7BK%7D%7BA%7D$ ，因為要是 $https://chart.googleapis.com/chart?cht=tx&chl=B%3E%5Cfrac%7BK%7D%7BA%7D$ 就代表 $AB>K$ 直接違反了題目的前提！

所以可以進一步優化 $B$ 的迴圈：

void solve() {
    int K;
    cin >> K;
    long long ans = 0;
    for (int A = 1; A <= K; ++A) {
        for (int B = 1; (long long)A * B <= K; ++B) {
            // 區間右界減去左界再加一
            ans += (K / A / B) - 1 + 1;
        }
    }
    cout << ans << "\n";
}

很神奇的是，這樣子就可以通過這題了，時間還只有幾毫秒而已！

那這樣子的時間複雜度是多少呢？

第一層迴圈會執行 $K$ 次毋庸置疑，但第二層迴圈的次數就比較怪了，每次都不一樣，這邊就需要稍微數學分析一下。

漸進複雜度數學分析

第二層迴圈的次數取決於 $A$ 的大小，第一輪會跑 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7BK%7D%7B1%7D$ 次、第二輪會跑 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7BK%7D%7B2%7D$ 次、第三輪會跑 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7BK%7D%7B3%7D$ 次...

因此第二層迴圈的次數可以如下估計

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7BK%7D%7B1%7D%2B%5Cfrac%7BK%7D%7B2%7D%2B%5Cfrac%7BK%7D%7B3%7D%2B%5Ccdots%2B%5Cfrac%7BK%7D%7BK%7D%3DK(%5Cfrac%7B1%7D%7B1%7D%2B%5Cfrac%7B1%7D%7B2%7D%2B%5Cfrac%7B1%7D%7B3%7D%2B%5Ccdots%2B%5Cfrac%7B1%7D%7BK%7D)%3DK%5Ccdot%5Csum_%7Bi%3D1%7D%5E%7BK%7D%5Cfrac%7B1%7D%7Bi%7D$

因為括號內的級數難以精確算出總和，不過我們只要估計上界就好了。

因此此時可以用一個小技巧，就是將級數內的元素分組後讓每組變成方便計算的模樣：

$https://chart.googleapis.com/chart?cht=tx&chl=K%5Ccdot%5Csum_%7Bi%3D1%7D%5E%7BK%7D%5Cfrac%7B1%7D%7Bi%7D%3DK%5B(%5Cfrac%7B1%7D%7B1%7D)%2B(%5Cfrac%7B1%7D%7B2%7D%2B%5Cfrac%7B1%7D%7B3%7D)%2B(%5Cfrac%7B1%7D%7B4%7D%2B%5Cfrac%7B1%7D%7B5%7D%2B%5Cfrac%7B1%7D%7B6%7D%2B%5Cfrac%7B1%7D%7B7%7D)%5Ccdots%5D$

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cle%20K%5B(%5Cfrac%7B1%7D%7B1%7D)%2B(%5Cfrac%7B1%7D%7B2%7D%2B%5Cfrac%7B1%7D%7B2%7D)%2B(%5Cfrac%7B1%7D%7B4%7D%2B%5Cfrac%7B1%7D%7B4%7D%2B%5Cfrac%7B1%7D%7B4%7D%2B%5Cfrac%7B1%7D%7B4%7D)%5Ccdots%5D%3DK%5B(1)%2B(1)%2B(1)%2B%5Ccdots%5D$

因為每一組內的加總值都變成了 1，於是現在問題轉換成了 $K$ 個東西按照上面的分組方式會被變成幾組？

按照我們的分組方式，每組內的元素數量如下表格：

第一組	第二組	第三組	第四組	$\cdots$
$1=2^0$	$2=2^1$	$4=2^2$	$8=2^3$	$\cdots$

我們令 $K$ 會被分成 $t$ 組，則按照等比級數和公式：

小提醒：因為我們是按照二的冪次來決定幾個元素一組的，因此若 $K$ 並非二的冪次減一，最後一組可能會填不滿，所以下面才會寫小於等於

$https://chart.googleapis.com/chart?cht=tx&chl=K%5Cle%5Cfrac%7B1(1-2%5Et)%7D%7B1-2%7D%3D%5Cfrac%7B-2%5Et%2B1%7D%7B-1%7D%3D2%5Et-1$

$\Rightarrow K+1\le2^t$

$\therefore t\ge\log_2{(K+1)}$

要知道之所以會是不等式，是因為最後一組分不滿的問題，所以其實滿足該不等式的最小值才會是我們 $t$ 的值，且因為分組數必為整數。因此可以推論 $t=\lceil\log_2{(K+1)}\rceil$

最後代回原式

$K\cdot t=K\cdot \lceil\log_2{(K+1)}\rceil=\mathcal{O}{(K\log K)}$

這就是我們的時間複雜度，這樣的複雜度在 $K=2\times 10^5$ 下為 $(2\times 10^5)\cdot \log_2{(2\times 10^5)}\approx 3521928$ ，對照我們 Day 4 的結論，2 秒內根本輕輕鬆鬆。

補充

實際上，剛剛那題還可以做到 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathcal%7BO%7D%7B(%5Csqrt%5B%5Cfrac%7B2%7D%7B3%7D%5D%7BK%7D)%7D$ ，做法我們可以先看 Atcoder 的 ABC227 C - ABC conjecture

題意

給定正整數 $N$ ，求有幾個正整數三元組 $(A, B, C)$ 能滿足 $A\le B\le C$ 且 $ABC\le N$ 。保證答案能小於 $2^{63}$ (答案在 long long 範圍內)。

$1\le N\le 10^{11}$
時間限制 2 秒

解法

這題跟剛剛幾乎一樣！只是輸入的數值範圍變大了超多、且多了一個條件 $A\le B\le C$ 而已。

一樣從最暴力開始看：

using ll = long long;

void solve() {
    ll N;
    cin >> N;
    
    ll ans = 0;
    for (ll A = 1; A <= N; ++A) {
        for (ll B = A; B <= N; ++B) {
            for (ll C = B; C <= N; ++C) {
                if (A * B * C <= N) ++ans;
            }
        }
    }
    
    cout << ans << "\n";
}

狀況幾乎與我們剛剛的情況很像，只是迴圈的次數不一樣了而已，因此我們一次分析到底囉！

而因為要滿足 $A\le B\le C$ 且 $ABC\le N$ ，所以要是 $A$ 本身大於 $\sqrt[3]{N}$ 的話就不可能有答案，所以 $A$ 允許的區間是 $[1, \sqrt[3]{N}]$
假設 $A$ 為已知，則 $https://chart.googleapis.com/chart?cht=tx&chl=ABC%5Cle%20N%5CRightarrow%20BC%5Cle%5Cfrac%7BN%7D%7BA%7D$ 又 $C\ge B$ ，因此 $B$ 不能超過 $https://chart.googleapis.com/chart?cht=tx&chl=%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D$ ，所以 $B$ 允許的區間是 $https://chart.googleapis.com/chart?cht=tx&chl=%5BA%2C%20%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D%5D$
假設 $A$ 、 $B$ 為已知，則 $https://chart.googleapis.com/chart?cht=tx&chl=ABC%5Cle%20N%5CRightarrow%20C%5Cle%5Cfrac%7BN%7D%7BAB%7D$ ，因此 $C$ 的區間會是 $https://chart.googleapis.com/chart?cht=tx&chl=%5BB%2C%20%5Cfrac%7BN%7D%7BAB%7D%5D$

按照以上三個結論，可以優化成：

using ll = long long;

void solve() {
    ll N;
    cin >> N;
    
    ll ans = 0;
    for (ll A = 1; A * A <= N / A; ++A) {
        for (ll B = A; B * B <= N / A; ++B) {
            // 區間右界減去左界再加一
            ans += N / A / B - B + 1;
        }
    }
    
    cout << ans << "\n";
}

這樣寫時間複雜度是 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathcal%7BO%7D%7B(%5Csqrt%5B%5Cfrac%7B2%7D%7B3%7D%5D%7BN%7D)%7D$ ，以這題的輸入 $10^{11}$ 而言兩秒內可以輕鬆通過。

ARC133 A 新解法

那剛剛那一題的解法能怎麼應用回去原本那題呢？

我們可以發現 ARC133_A 這題的三元組若排列不同則算是不同的三元組、但是 ABC227_C 的三元組限制必須由小到大，那我們是不是只要計算目前「由小到大」的三元組可以生成多少個排列，加總後就可以把 ABC227_C 的解法用到 ARC133_A 去？

我們可以先分析看看不同情況下會生成多少個排列：

$A = B = C$ ：生成一個排列
$A = B \neq C$ ：生成三個排列
$A \neq B = C$ ：生成三個排列
$A \neq B \neq C$ ：生成六個排列

而因為我們程式中沒有實際的枚舉每一個 $C$ ，而是找出合格的區間然後直接相減計算，因此我們只能在已知 $A$ 、 $B$ 的情況下計算

這邊重貼一次 $ABC$ 各自的區間範圍

$A$ 的區間是 $[1, \sqrt[3]{N}]$
$B$ 的區間是 $https://chart.googleapis.com/chart?cht=tx&chl=%5BA%2C%20%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D%5D$
$C$ 的區間是 $https://chart.googleapis.com/chart?cht=tx&chl=%5BB%2C%20%5Cfrac%7BN%7D%7BAB%7D%5D$

首先因為我們在 $B$ 的迴圈內， $A$ 和 $B$ 是已知，因此可以很簡單的判斷 $A$ 是否等於 $B$ ； $C$ 的部分則可以藉由判斷它的上界 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7BN%7D%7BAB%7D$ 是否等於下界 $B$ ，若是等於就代表只有一個 $B=C$ 的情況；若不等於則代表有一個 $B=C$ 的情況、其他則都是 $B\neq C$ 的情況。因此程式可以如下撰寫：

using ll = long long;

void solve() {
    ll N;
    cin >> N;
    
    ll ans = 0;
    for (ll A = 1; A * A <= N / A; ++A) {
        for (ll B = A; B * B <= N / A; ++B) {
            ll bound = N / A / B;
            if (A == B) {
                if (B == bound) ans += 1;
                else ans += (bound - B + 1) * 3 - 2;
            } else {
                if (B == bound) ans += 3;
                else ans += (bound - B + 1) * 6 - 3;
            }
        }
    }
    
    cout << ans << "\n";
}

如此一來就可以以 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathcal%7BO%7D%7B(%5Csqrt%5B%5Cfrac%7B2%7D%7B3%7D%5D%7BK%7D)%7D$ 的時間複雜度通過 ARC133 A ，但是因為它輸入只有到 $2\times 10^5$ ，所以從執行時間上你看不出速度差距就是了。