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

2023 iThome 鐵人賽

DAY 8

自我挑戰組

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

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

暗魂駭客

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

2023-09-23 22:34:03

675 瀏覽

分享至

今天要繼續介紹時間複雜度的常用分析手法，文章內容參考了各種網路資源，其中最主要的是 AA 競程在 YouTube 的時間複雜度教學影片，有興趣的可以去他們的 YT 頻道看看。

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

不過首先我會把昨天 ARC133 A 新解法的時間複雜度分析補上：

ARC133 A 新解法時間複雜度分析

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";
}

大致觀察後，可以發現外層迴圈的步驟數是 $\mathcal{O}{(\sqrt[3]{N})}$ ，內層迴圈的操作數取決於 $A$ 的大小，目前只大概知道會跑 $https://chart.googleapis.com/chart?cht=tx&chl=%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1$ 次，至於迴圈內的程式碼都是 $\mathcal{O}{(1)}$ 。因此難點在第二層迴圈，需要一些數學分析。

按照上面的觀察，對於迴圈最內層會跑的次數可以列式如下：

$https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7BA%3D1%7D%5E%7B%5Csqrt%5B3%5D%7BN%7D%7D%7B%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1%7D$

要知道其實我們也不需要真的算出這條式子，只要估計它的上界就可以了，因此可以這樣做：

$https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7BA%3D2%7D%5E%7B%5Csqrt%5B3%5D%7BN%7D%7D%7B%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1%7D%5Cle%20%5Cint_%7B1%7D%5E%7B%5Csqrt%5B3%5D%7BN%7D%7D%7B%28%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1%29%5C%2C%20dA%7D$

（注意求和符號中的 A 是從 2 開始）
然後先算出不定積分

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cint%7B%28%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1%29%5C%2C%20dA%7D%3D%5Cint%7B%28%28N%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%5Ccdot%20A%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7D%29-A%2B1%29%5C%2C%20dA%7D$
$https://chart.googleapis.com/chart?cht=tx&chl=%3D%282%5Ccdot%20N%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%5Ccdot%20A%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D-%5Cfrac%7B1%7D%7B2%7DA%2BA%29%2BC%3D%282%5Csqrt%7BAN%7D-%5Cfrac%7BA%7D%7B2%7D%2BA%29%2BC$

（ $C$ 是積分常數）
再算定積分

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cint_%7B1%7D%5E%7B%5Csqrt%5B3%5D%7BN%7D%7D%7B%28%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1%29%5C%2C%20dA%7D%3D%282%5Csqrt%7BAN%7D-%5Cfrac%7BA%7D%7B2%7D%2BA%29%5Cmid%5E%7B%5Csqrt%5B3%5D%7BN%7D%7D_%7B1%7D$
$https://chart.googleapis.com/chart?cht=tx&chl=%3D%282%5Csqrt%7B%5Csqrt%5B3%5D%7BN%7D%5Ccdot%20N%7D-%5Cfrac%7B%5Csqrt%5B3%5D%7BN%7D%7D%7B2%7D%2B%5Csqrt%5B3%5D%7BN%7D%29-%282%5Csqrt%7BN%7D-%5Cfrac%7B1%7D%7B2%7D%2B1%29$
$https://chart.googleapis.com/chart?cht=tx&chl=%3D2N%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D-2N%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%2B%5Cfrac%7B1%7D%7B2%7DN%5E%7B%5Cfrac%7B1%7D%7B3%7D%7D%2B%5Cfrac%7B1%7D%7B2%7D%3D%5Cmathcal%7BO%7D%7B%28N%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D%29%7D$

積分之所以會大於等於求和是因為定積分算是一種連續平滑的求和，就像下圖表示的那樣

不過可以注意到剛剛的算式我們把求和算式中 A 的起始值變成 2，這是因為當 N 從 1 開始時，求和會大於定積分，不過我們可以把它當特例先暫時忽略，之後再加回來就好，因此有：

$https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7BA%3D1%7D%5E%7B%5Csqrt%5B3%5D%7BN%7D%7D%7B%5Csqrt%7B%5Cfrac%7BN%7D%7BA%7D%7D-A%2B1%7D%5Cle%20%5Cmathcal%7BO%7D%7B%28N%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D%29%7D%20%2B%20%28%5Csqrt%7BN%7D-1%2B1%29%3D%5Cmathcal%7BO%7D%7B%28N%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D%29%7D$

如此一來就證明完成，時間複雜度為 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathcal%7BO%7D%7B%28N%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D%29%7D$ ，這樣的時間複雜度在 ARC133 A 中 $N\le 2\times 10^5$ 的數值下超級低，低到基本上看不出與原解法 $\mathcal{O}{(N\log N)}$ 的時間差距

數學分析的更多練習

練習一

請問下面程式碼的時間複雜度是什麼？

int func(int n) {
    int result = 0;
    while (n > 0) {
        for (int i = 0; i < n; ++i) {
            // 某些跟 result 有關的 O(1) 操作
        }
        n /= 2;
    }
    return result;
}

首先從外面的 while 迴圈開始看，它的執行次數是 n 能被除以 2 的次數，這不就是對數的定義嗎？因此 while 迴圈內的東西至少會跑 $\mathcal{O}{(\log n)}$ 次。

至於裡面的 for 迴圈會跑的次數是取決於當下的 n ，這比較難處理，因此我們可以先列出前面幾次來觀察：

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7Bn%7D%7B1%7D%2C%20%5Cfrac%7Bn%7D%7B2%7D%2C%20%5Cfrac%7Bn%7D%7B4%7D%2C%20%5Cfrac%7Bn%7D%7B8%7D%2C%20%5Ccdots$

以上是我們內層 for 迴圈會跑的次數，仔細看會發現這就只是等比級數而已，所以我們可以直接套用級數和的公式計算。

我們已經知道了 while 迴圈會跑 $\log_2{n}$ 次，這代表等比級數有 $\log_2{n}$ 項，因此可以如下計算：

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7Bn%7D%7B1%7D%2B%5Cfrac%7Bn%7D%7B2%7D%2B%5Cfrac%7Bn%7D%7B4%7D%2B%5Cfrac%7Bn%7D%7B8%7D%2B%5Ccdots$

$https://chart.googleapis.com/chart?cht=tx&chl=%3D%5Cfrac%7Bn%281-%28%5Cfrac%7B1%7D%7B2%7D%29%5E%7B%5Clog_2%7Bn%7D%7D%29%7D%7B1-%5Cfrac%7B1%7D%7B2%7D%7D%3D%5Cfrac%7Bn%281-2%5E%7B-%5Clog_2%7Bn%7D%7D%29%7D%7B%5Cfrac%7B1%7D%7B2%7D%7D%3D%5Cfrac%7Bn%281-%5Cfrac%7B1%7D%7Bn%7D%29%7D%7B%5Cfrac%7B1%7D%7B2%7D%7D%3D2%28n-1%29%3D%5Cmathcal%7BO%7D%7B%28n%29%7D$

因此這段程式的時間複雜度是 $\mathcal{O}{(n)}$

不過因為漸進複雜度在分析的是函數的量級，所以 $n$ 的大小不是有限的數字，因此剛剛其實也能用無窮等比級數公式來計算：

無窮等比級數公式： $https://chart.googleapis.com/chart?cht=tx&chl=S_%5Cinfty%3D%5Cfrac%7Ba%7D%7B1-r%7D$ ，1 減公比分之首項
更多資訊請參考維基百科等比數列條目

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7Bn%7D%7B1%7D%2B%5Cfrac%7Bn%7D%7B2%7D%2B%5Cfrac%7Bn%7D%7B4%7D%2B%5Cfrac%7Bn%7D%7B8%7D%2B%5Ccdots%3D%5Cfrac%7Bn%7D%7B1-%5Cfrac%7B1%7D%7B2%7D%7D%3D2n%3D%5Cmathcal%7BO%7D%7B%28n%29%7D$

結果是一樣的

練習二

請問下面程式碼的時間複雜度是什麼？

int func(int n) {
    int result = 0;
    while (n > 1) {
        // 某些跟 result 有關的 O(1) 操作
        n = (int)sqrt(n);
    }
    return result;
}

因為 sqrt 回傳 double 被我們強制轉型成 int，這樣做等同是開根號後再做向下取整，因此到 n <= 3 時開根號就會直接變 1，不會無窮迴圈

關於這段程式，可以觀察到程式執行的次數取決於 n 能被開幾次根號才會小於等於 3 ？，因為有點難分析，所以我們可以先列出前幾次的 n 觀察一下：

$https://chart.googleapis.com/chart?cht=tx&chl=n%2C%20n%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%2C%20n%5E%7B%5Cfrac%7B1%7D%7B2%7D%5Ccdot%20%5Cfrac%7B1%7D%7B2%7D%7D%2C%20n%5E%7B%5Cfrac%7B1%7D%7B2%7D%5Ccdot%20%5Cfrac%7B1%7D%7B2%7D%5Ccdot%20%5Cfrac%7B1%7D%7B2%7D%7D%5Ccdots%5CRightarrow%20n%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%2C%20n%5E%7B%5Cfrac%7B1%7D%7B4%7D%7D%2C%20n%5E%7B%5Cfrac%7B1%7D%7B8%7D%7D%2C%20%5Ccdots$

可以注意到其實開根號等同是在次方不斷除以 2，因此 while 迴圈的次數其實大約會是 n 能在次方被除以 2 幾次才會小於等於 3 ？

之所以講"大約"是因為每次開根號都會被向下取整，所以其實很難找出精確的次數，我們這樣只能算是估計而已

那我們就先令 $t$ 代表 while 迴圈會跑的次數，按照剛才觀察的結論，可列式如下：

$https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7B%5Cfrac%7B1%7D%7B2%5Et%7D%7D%5Cle%203%5CRightarrow%20n%5Cle%203%5E%7B2%5Et%7D%5CRightarrow%202%5Et%5Cge%5Clog_3%7Bn%7D%5CRightarrow%20t%5Cge%5Clog_2%7B%5Clog_3%7Bn%7D%7D$

（t 是在次方的位置喔！不知道為什麼這邊的數學式渲染得有點擠XD）

因為 while 迴圈的執行次數是跑幾次 n 能小於等於 3 ？，這其實就是在問最少需要跑幾次， n 才能小於等於 3 ？，因此我們的執行次數是滿足不等式中的最小的 $t$ ，即為 $\log_2{log_3{n}}=\mathcal{O}{(\log\log n)}$ 。

因此這段程式的時間複雜度是 $\mathcal{O}{(\log\log n)}$ ，這種時間複雜度超級小，而且很少見。

話說埃拉托斯特尼篩法的時間複雜度是 $\mathcal{O}{(n\log\log n)}$ ，有興趣的可以去它的維基百科條目看看

練習三

int func(int n) {
	int result = 0;
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = i; j; j = (j - 1) & i) {
			// 某些跟 result 有關的 O(1) 操作
		}
	}
	return result;
}

我知道這次的練習乍看之下很可怕XD，主要是那些位元運算可能會讓人很疑惑，因此這邊會先稍微解釋一下它在做什麼：

for (int i = 0; i < (1 << n); ++i) ：
(1 << n) 的意思是 $2^n$ ，因此這行的意思就是讓 i 從 $0$ 遍歷到 $2^n-1$
for (int j = i; j; j = (j - 1) & i)：
首先你可以自己試著算算看 i & (i - 1) 會是什麼結果？你會發現這個算式把 i 在二進位表示下最低位的 1 給拿掉了，因為減 1 會把一個數從二進位表示下最低位的 1 開始，把後面的所有 bit 翻轉。
就像 0b111{10000} - 0b00000001 = 0b111{01111} 大括號內的 bit 被翻轉了
而翻轉之後再和原來的自己做 and 運算則會把最低位的 1 給拿掉。
那 for (int j = i; j; j = (j - 1) & i) 就比較特別了，它是在枚舉當前 i 在二進位表示下所有的 1 所能形成的非空子集合。
它的原理是 j 每次減一會讓它從二進位表示下的最低位開始以後的 bit 全部翻轉。而這樣的數字去和 i 做 and 會導致最低位的 1 被拿掉、但最低位以後曾經是 1 的 bit 會被拿回來。
聽起來很繞口，因此用實際例子展示：
```
i = 26               (0b11010)
j = i
j = (j - 1) & i = 24 (0b11000)
j = (j - 1) & i = 18 (0b10010)
j = (j - 1) & i = 16 (0b10000)
j = (j - 1) & i = 10 (0b01010)
j = (j - 1) & i =  8 (0b01000)
j = (j - 1) & i =  2 (0b00010)
```
你會發現 26 在二進位表示下出現的那三個 1 所能組成的所有非空子集合都出現過一遍了。

解釋完之後我們就可以開始分析了。

首先可以觀察到外層迴圈會跑 $2^n$ 次，內層迴圈則取決於 $i$ 在二進位表示下的 1 的有多少種非空的子集合，如果用 $popcount(i)$ 表示 $i$ 二進位表示下 1 的數量，那非空子集合的數量就是 $2^{popcount(i)}-1$ 。

若從一個有 $n$ 個元素的集合中選出一個子集合，則對於集合內的每個元素都有"選它"、"不選它"兩種選項，因此共有 $2^n$ 種子集，這時再去掉誰都不選的空集合，就可以知道非空子集合的數量會是 $2^n-1$

然後我們前面都是先列式出來後才成功分析複雜度的，但現在狀況要怎麼列式呢？ $popcount(i)$ 只是我們定義的一個函數，要怎麼算出來可還沒有解決呢！而且我們又沒辦法推算 $[0, 2^n-1]$ 之中的數在二進位表示下 1 的數量...怎麼辦，卡關了？

既然如此不如換一種思路來想：既然我們沒辦法知道每個數在二進位表示下 1 的數量，那我們能不能知道 $[0, 2^n-1]$ 中有幾個數在二進位表示下剛好有 k （假設 k 為某特定位元數）個 1 呢？值得一試！

先觀察看看區間 $[0, 2^4-1]$ 的狀況：

請問在 $[0, 2^4-1]$ 中有幾個數在二進位表示下有 0 個 1？零個！
請問在 $[0, 2^4-1]$ 中有幾個數在二進位表示下有 1 個 1？四個！
請問在 $[0, 2^4-1]$ 中有幾個數在二進位表示下有 2 個 1？六個！
請問在 $[0, 2^4-1]$ 中有幾個數在二進位表示下有 3 個 1？四個！
請問在 $[0, 2^4-1]$ 中有幾個數在二進位表示下有 4 個 1？一個！

有沒有發現什麼？對於 $[0, 2^n-1]$ 範圍內的數，在二進位表示下有 k 個 1 的數字會有 $C^n_k$ 個！其實這件事蠻好理解的，因為把已知的 k 個 1 擺進 n 個位元裡面，相當於從 n 個座位裡面抽出 k 個座號，而這不就正好是組合數的概念嗎？

因此按照我們發現的規則，對於前幾次內層迴圈的次數，我們可以先列出來觀察

$C^n_0\cdot (2^0-1), C^n_1\cdot (2^1-1), C^n_2\cdot (2^2-1), C^n_2\cdot (2^2-1)\cdots$

整理一下可以得出這條式子：

$\Rightarrow \sum_{i=0}^{n}{C^n_i\cdot (2^i-1)}$

乍看之下是不是完全沒有頭緒？是不是完全不知道要怎麼化簡含有組合數的式子？

沒關係我們先把式子分開來看一下

$\sum_{i=0}^{n}{C^n_i\cdot (2^i-1)}=\sum_{i=0}^{n}{C_i^n\cdot 2^i}-\sum_{i=0}^{n}{C_i^n}$

OH YA！還是沒想法...這種時候去維基百科翻翻看有沒有好的性質是很棒的做法XD

從二項式定理的條目看到 $(1+x)^n=\sum_{k=0}^{n}{C_k^n\cdot x^k}$
從巴斯卡三角形的條目的第五和第六條性質可以推出 $\sum_{k=0}^{n}{C_k^n}=2^n$

啊哈！有想法了，所以剛剛那條式子的左項可以變成：

$\sum_{i=0}^{n}{C_i^n\cdot 2^i}=(1 + 2)^n=3^n$

右項可以變成：

$\sum_{i=0}^{n}{C_i^n}=2^n$

所以結論就是：

$\sum_{i=0}^{n}{C_i^n\cdot 2^i}-\sum_{i=0}^{n}{C_i^n}=3^n-2^n=\mathcal{O}{(3^n)}$

因此這段程式的時間複雜度是 $\mathcal{O}{(3^n)}$

這段程式一般都用在動態規劃的枚舉子集中，每個 bit 會代表三種狀態（不在集合內、在集合內但還沒被枚舉到、在集合內且正在枚舉），如想了解更多可以參考： OI-wiki 、 CSDN 状态压缩动态规划（状压DP）及枚举子集优化

小結

今天做了好幾個數學分析時間複雜度的練習，相信各位已經相當熟悉數學分析的技巧了。
~~但算數學真的好累~~

明天將會帶給各位最後一個時間複雜度的分析技巧，請各位敬請期待囉！

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

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

系列文

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

RSS系列文訂閱系列文

6 人訂閱

完整目錄

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

尚未有邦友留言

立即登入留言

參賽組數

1064 組

團體組數

40 組

累計文章數

22195 篇

完賽人數

600 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙

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