時間復雜度計算（以for循環為例）

本文理論內容來自嚴蔚敏版《數據結構(C語言版第2版)》

*本文僅為復習時的總結，描述不準確、過程不嚴謹之處，還請理解

一、算法的相關概念

首先復習一下算法的定義及5個重要特性

其次是算法的評價標準

可以看到? 時間復雜度? 屬于算法評價標準中的高效性

??

二、時間復雜度的相關概念

下面介紹一些時間復雜度的相關概念

如果不考慮計算機的軟硬件等環境因素

影響算法時間代價的最主要因素是問題規模（用非負整數 n 表示， $n \geqslant 0$ ）

問題規模是算法求解問題輸入量的多少，是問題大小的本質表示

比如輸入2個數排序、3個數排序、4個數排序，問題規模(n)?逐漸增大，執行時間也逐漸增加

再來看執行時間

對語句的執行時間進行拆解：

語句的重復執行次數?稱作?語句頻度（用? $f(n)$ ?表示）

算法中能使語句重復執行的結構通常是循環結構，所以本文以for循環為例

為了簡化分析，假設?每條語句執行一次所需的時間?均是?單位時間

所以?語句的執行時間=語句頻度×單位時間

同理算法的執行時間=所有語句頻度之和×單位時間（即提取公因式 "單位時間" ）

由于?單位時間?是定值

因此?算法的執行時間與?所有語句頻度之和?成正比

對于稍微復雜一些的算法，計算所有語句頻度之和通常是比較困難的

因此，我們引入基本語句的概念，用于度量算法的工作量

基本語句指的是對算法的執行時間貢獻最大的語句，它的語句頻度?與?算法的執行時間成正比

*為了方便描述，例題均以for循環為例，僅寫出主要代碼

如果不太了解for循環可以先看我的這篇文章——

《?for、while、do while循環的流程圖表示及相應continue、break的流程圖表示?》

for循環可以理解為

for( 循環變量初始化 ; 循環條件 ; 循環變量自增 )
{循環體
}

舉例：for循環求1到100的和

for( i=1; i<=100; i++ )
{sum+=i;
}

對應關系

???

【例1】有以下代碼，輸入n代表問題規模（在后續例題中，此點將不再贅述），計算for循環體語句頻度之和

int n,i,j,k;
int a=0,b1=0,b2=0,c1=0,c2=0,c3=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{a++;for(j=1; j<=n; j++){b1++;b2++;for(k=1; k<=n; k++){c1++;c2++;c3++;}}
}

在第一層for循環體中，只有1條語句：a++;

循環變量 i 從1到n，循環共執行 $n$ 次

所以第一層for循環體的語句頻度=循環體語句條數 x 循環執行次數=? $1\times n=n$

在第二層for循環體中，有2條語句：b1++; b2++;

循環變量 i 從1到n，循環變量 j 從1到n，循環共執行 $n\times n=n^{2}$ 次

所以第二層for循環體的語句頻度=循環體語句條數 x 循環執行次數=? $2\times n^{2}=2n^{2}$

在第三層for循環體中，有3條語句：c1++; c2++; c3++;

循環變量 i 從1到n，循環變量 j 從1到n，循環變量 k?從1到n，循環共執行 $n\times n\times n=n^{3}$ 次

所以第三層for循環體的語句頻度=循環體語句條數?x 循環執行次數=? $3\times n^{3}=3n^{3}$

所以for循環體語句頻度之和為? $f(n)=3n^{3} +2n^{2} +n$

當問題規模(n)趨于無窮大時

$\lim\limits_{n \to \infty}\frac{f(n)}{n^{3}}=\lim\limits_{n \to \infty}\frac{3n^{3}+2n^{2}+n}{n^{3}}=3$

因為3是常數，所以 $f(n)$ ?與? $n^{3}$ ?同階（或稱? $f(n)$ ?的數量級為? $n^{3}$ ）

時間復雜度? $T(n)$ ?用語句頻度的數量級來表示（大 $O$ 表示法）

大 $O$ 表示法在數學上的定義：

? $T(n)$ ?和? $f(n)$ ?都是定義在正整數集合上的函數

若存在正的常數： $c$ ?和? $n_{0}$ ，對于所有? $n\ (n\geqslant n_{0})$ ，?均滿足不等式? $0\leqslant T(n)\leqslant c\cdot f(n)$

則記作? $T(n)=O (f(n))$

該定義用? $f(n)$ ?來漸近表示時間復雜度? $T(n)$

從圖中可以看出時間復雜度? $T(n)$ ?的增長至多趨向于? $f(n)$ 的增長

換句話說，大 $O$ 表示法? $O (f(n))$ ?給出的是時間復雜度的一個漸近上界? $f(n)$

【例1】的語句頻度之和為? $f(n)=3n^{3} +2n^{2} +n$ ，數量級為? $n^{3}$ ?，則時間復雜度為? $O(n^{3})$

可以看到語句頻度中起主要作用的是? $3n^{3}$

對應第三層for循環體的3條語句：c1++; c2++; c3++;?

則這3條語句是對算法的執行時間貢獻最大的語句（即基本語句）

所以計算時間復雜度時，無需計算所有語句的語句頻度，只需計算基本語句的語句頻度，得出數量級即可

計算時間復雜度的步驟：

1.找出基本語句

2.計算基本語句的語句頻度

3.省略系數和無關項，得出數量級，即為時間復雜度

??

三、求和式及其運算規則

在計算時間復雜度之前，需要先了解求和式? $\sum\limits_{i=1}^{n} a_{i}$

如果不太了解求和式可以先看我的這篇文章——《求和式及其運算規則》

? ?

求和符號 $\sum$ ?（讀作sigma）

求和下限? $i=1$ ?：代表求和變量? $i$ ?從1開始遞增

求和上限? $n$ ?：代表遞增到n結束

求和表達式? $a_{i}$ ：?一般是通項公式（只不過是把通項下標符號從 n 換成 i 而已）

求和變量? $i$ ?從1遞增到n，則求和表達式? $a_{i}$ ?從? $a_{1}$ 變化到? $a_{n}$

求和式整體即從? $a_{1}$ ?累加到? $a_{n}$ ：?? $\sum\limits_{i=1}^{n} a_{i}=a_{1}+a_{2}+a_{3}+\cdots+a_{n-1}+a_{n}$

如果學過for循環就很好理解了

for(i=1; i<=n; i++)
{sum+=a[i];
}

$i=1$ ?時：當前項? $a_{i}=a_{1}$ ，求和sum=? $a_{1}$ ，i++自增到2

$i=2$ ?時：當前項? $a_{i}=a_{2}$ ，求和sum=? $a_{1}+a_{2}$ ，i++自增到3

$i=3$ ?時：當前項? $a_{i}=a_{3}$ ，求和sum=? $a_{1}+a_{2}+a_{3}$ ，i++自增到4

……

$i=n-1$ ?時：當前項? $a_{i}=a_{n-1}$ ，求和sum=? $a_{1}+a_{2}+a_{3}+\cdots+a_{n-1}$ ，i++自增到n

$i=n$ ?時：當前項? $a_{i}=a_{n}$ ，求和sum=? $a_{1}+a_{2}+a_{3}+\cdots+a_{n-1}+a_{n}$ ，i++自增到n+1

$i=n+1$ ?時：i<=n為假，循環結束

最終求和sum的值：? $sum=\sum\limits_{i=1}^{n} a_{i}=a_{1}+a_{2}+a_{3}+\cdots+a_{n-1}+a_{n}$

求和式的數乘規則（提取常數）：

$\sum\limits_{i=1}^{n} (c\cdot a_{i})=c\sum\limits_{i=1}^{n} a_{i}$ ?（其中c為常數）

求和式的加法規則（減法同理）：

$\sum\limits_{i=1}^{n} (a_{i}+b_{i})=\sum\limits_{i=1}^{n} a_{i}+\sum\limits_{i=1}^{n} b_{i}$

求和式的分段規則：

$\sum\limits_{i=1}^{n}a_{i}=\sum\limits_{i=1}^{m}a_{i}+\sum\limits_{i=m+1}^{n}a_{i}$ （其中? $1\leqslant m< m+1\leqslant n$ ）

求和式的上下限變換規則：

$\sum\limits_{i=1}^{n} a_{i}=\sum\limits_{i=1+k}^{n+k} a_{i-k}$

上述規則為簡便起見，求和上下限都是從1到n

實際遇到的求和式上下限不一定是從1到n

有可能是從0到k，從m到n+1，從0到n-1-i，……

但是均適用上述規則

四、嵌套無關循環和嵌套相關循環

下面區分一下嵌套無關循環和嵌套相關循環

（有點類似于SQL的不相關子查詢和相關子查詢）

【例2】嵌套無關循環，內層循環條件與外層循環變量無關

int n,i,j;
int a=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{for(j=1; j<=n; j++){a++;}
}

可以看到內層循環條件是 j<=n，j 從1到n，執行n次

無論外層循環變量 i 取何值，每輪內層循環都會執行n次

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\Large \sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n}1=n \times n=n^{2}$

3.時間復雜度： $T(n)=O(n^{2})$

解釋一下，這里的語句頻度是怎么列式出來的

嵌套無關循環，所以內外層循環互不干擾，語句頻度獨立計算

因為外層循環條件是 i<=n?，所以?i 能取的最大值（即求和上限）是：n

因為外層循環變量初始化是 i=1，所以 i 能取的最小值（即求和下限）是：1

（通常情況，求和下限直接照抄循環變量初始化即可，后續不再贅述）

而內層循環可以看作是外層循環體的1條基本語句，則求和表達式（通項公式）是1

所以外層循環的語句頻度為

$\sum\limits_{i=1}^{n}1 =\overbrace{1+\cdots +1}^{n} = n$

?

因為內層循環條件是 j<=n?，所以?j?能取的最大值（即求和上限）是：n

內層循環體只有1條基本語句：a++;? 則求和表達式（通項公式）是1

所以內層循環的語句頻度為

$\sum\limits_{j=1}^{n}1 =\overbrace{1+\cdots +1}^{n} = n$

?

只有當內外層循環都結束時，算法才結束

（即算法結束需要分內層循環、外層循環兩個步驟）

根據統計學的乘法原理，需要把二者相乘得

$\sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n}1=n \times n=n^{2}$

語句頻度是? $n^{2}$ ，數量級為? $n^{2}$ ?，則時間復雜度為? $O(n^{2})$

其實【例1】就是嵌套無關循環，再把【例1】的代碼貼過來

int n,i,j,k;
int a=0,b1=0,b2=0,c1=0,c2=0,c3=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{a++;for(j=1; j<=n; j++){b1++;b2++;for(k=1; k<=n; k++){c1++;c2++;c3++;}}
}

按現在的步驟重新計算時間復雜度

1.基本語句：

c1++;

c2++;

c3++;

2.基本語句的語句頻度： $\sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n}1 \times \sum\limits_{k=1}^{n}3=n \times n \times 3n=3n^{3}$

3.時間復雜度： $T(n)=O(n^{3})$

解釋一下，這里的語句頻度是怎么列式出來的

嵌套無關循環，所以內外層循環互不干擾，語句頻度獨立計算

將前兩層循環與第三層循環分開計算：

因為內層循環可以看作是外層循環體的1條基本語句

所以前兩層循環可以直接參考【例2】，列式為

$\sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n}1$

基本語句是對算法的執行時間貢獻最大的語句

所以基本語句是第三層循環體中的3條語句：c1++; c2++; c3++;??

所以第三層循環的求和表達式（通項公式）是3，列式為

$\sum\limits_{ k=1}^{n}3 =\overbrace{3+\cdots +3}^{n} = 3n$

將其展開，其實就是n個3相加，結果為3n

或者根據求和式的數乘規則，將常數提出

$\sum\limits_{ k=1}^{n}3=3\sum\limits_{ k=1}^{n}1 =3\times (\overbrace{1+\cdots +1}^{n}) =3\times n = 3n$ ?

提取常數可以理解為乘法分配律的逆運算?

$c\times a+c\times b=c\times (a+b)$

將a=1, b=1, c=3代入得

$3\times 1+3\times 1=3\times (1+1)$

只不過現在不是2項，而是n項?

$\overbrace{3\times1+\cdots+3\times1}^{n}=3\times (\overbrace{1+\cdots+1}^{n})=3\sum\limits_{ i=1}^{n}1$

根據統計學的乘法原理，將前兩層求和式與第三層求和式相乘得語句頻度

$\sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n}1 \times \sum\limits_{k=1}^{n}3=n \times n \times 3n=3n^{3}$

雖然語句頻度是? $3n^{3}$ ，但省略系數后，數量級為? $n^{3}$ ?，則時間復雜度為? $O(n^{3})$

【例3】嵌套相關循環，內層循環條件與外層循環變量相關

int n,i,j;
int a=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{for(j=1; j<=i; j++){a++;}
}

可以看到內層循環條件是 j<=i，j 從1到 i，執行 i 次

當外層循環變量 i 的值發生改變時，內層循環的執行次數也會隨之改變

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} 1=\sum\limits_{i=1}^{n} i=1+2+\cdots +n=\frac{n(n+1)}{2}$

3.時間復雜度： $T(n)=O(n^{2})$

解釋一下，這里的語句頻度是怎么列式出來的

因為是嵌套相關循環，內外層循環相關，不能分開計算

因為外層循環條件是 i<=n ，所以?i 能取的最大值（即求和上限）是：n

因為內層循環條件是 j<=i ，所以?j?能取的最大值（即求和上限）是：i

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} 1$

雙重求和可以加括號以區分

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} 1=\sum\limits_{i=1}^{n} (\sum\limits_{j=1}^{i} 1)$ ?

可以類比復合函數，先計算括號內的

$\sum\limits_{j=1}^{i}1 =\overbrace{1+\cdots +1}^{i} = i$

（這里只不過是把求和上限從n變成 i，與前面本質相同，就是 i 個1相加）

將括號內的求和式替換為計算結果，雙重求和變為?

$\sum\limits_{i=1}^{n} (\sum\limits_{j=1}^{i} 1)=\sum\limits_{i=1}^{n} i$

注意，當求和變量? $i$ 與通項公式 $a_{i}$ 的下標是相同符號時，代表累加的項隨求和變量進行變化（如下所示）

$\sum\limits_{i=1}^{n} a_{i}=a_{1}+a_{2}+a_{3}+\cdots + a_{n}$

本題比較特殊，通項公式就是求和變量：? $a_{i}=i$

$\sum\limits_{i=1}^{n} i=1+2+3+\cdots +n$

求和變量 i 從 1 到 n，則通項公式也是從 1 到 n，求和式整體即從1累加到n

此時變為等差數列求和，代入等差數列求和公式?

$S_{n}=\frac{n(a_{1}+a_{n})}{2}$ ?

得到語句頻度

$\sum\limits_{i=1}^{n} i=1+2+3+\cdots +n=\frac{n(n+1)}{2}$

將其展開得

$\frac{n(n+1)}{2}=\frac{1}{2}n^{2}+\frac{1}{2}n$

省略系數和無關項后，數量級為? $n^{2}$ ，則時間復雜度為? $O(n^{2})$

五、常見的時間復雜度

下面介紹常見的時間復雜度

將各時間復雜度當作函數，里面的自變量n就是問題規模

因為問題規模(n)是描述問題大小的非負整數? $(n\geqslant 0)$

所以比較時間復雜度只需看第一象限

比較時間復雜度，通常按問題規模(n)趨于無窮大（ $n \to \infty$ ）來比較

所以常見時間復雜度關系如下：

$\begin{matrix} O(2^n)>O(n^3)>O(n^2)>O(nlog_{2}n)>O(n)>O(\sqrt{n})>O(log_{2}n)>O(1) \end{matrix}$

但是上圖為了看清每個函數的趨勢，對自變量問題規模(n)的取值范圍過小，導致誤解

誤解一：對? $2^{n}$ ?和? $n^{3}$ ?的增長速率產生誤解

下面將? $2^{n}$ ?和? $n^{3}$ ?單獨畫出，并擴大取值范圍

可以看到? $2^{n}$ ?和? $n^{3}$ ?這兩個函數在第一象限有兩個交點

一個交點在? $n \in[1,2]$ ?區間內（如果看不清可以看第一張函數圖）

另一個交點在? $n \in[9,10]$ ?區間內

在第二次相交后， $2^{n}$ ?的增長速率明顯要比? $n^{3}$ ?快?

所以當問題規模(n)趨于無窮大時： $O(2^n)>O(n^3)$

誤解二：對? $\sqrt{n}$ ?和? $log_{2}n$ ?的增長速率產生誤解

在第一張函數圖中這兩個函數圖像幾乎重合

下面將? $\sqrt{n}$ ?和? $log_{2}n$ ?單獨畫出來，并擴大取值范圍

可以看到? $\sqrt{n}$ ?和? $log_{2}n$ ?這兩個函數在第一象限有兩個交點（4，2）和（16，4）

在第二次相交后，? $\sqrt{n}$ ??的增長速率明顯要比? $log_{2}n$ ?快?

所以當問題規模(n)趨于無窮大時： $O(\sqrt{n})>O(log_{2}n)$

題目選項可能會把? $\sqrt{n}$ ?寫成冪次形式? $n^{\frac{1}{2}}$ ?，上式變為： $O(n^{\frac{1}{2}})>O(log_{2}n)$

? ??

（一）常數階

【例4.1】常數階? $O(1)$ ?

int i,x=0,s=0;
for(i=0;i<1000;i++)
{x++;s+=x;
}

這個例子是我特意挑的

因為它的for循環從0開始，循環條件是<

而前面的for循環都是從1開始，循環條件是<=

計算時間復雜度

1.基本語句：

x++;?

s+=x;

2.基本語句的語句頻度： $\sum\limits_{i=0}^{999} 2=\sum\limits_{i=1}^{1000} 2=\overbrace{2+\cdots + 2}^{1000} =2000$

3.時間復雜度： $T(n)=O(1)$

因為循環條件是 i<1000?，所以?i 能取的最大值（即求和上限）是：1000-1=999

0—999和1—1000在循環的執行次數沒有區別，都是1000次

如果反應不過來，那就將0—999同時加1

相當于在數軸上將0—999整體向右移1個單位，得到1—1000

比如1—5就執行5次，1—200就執行200次，1—1000就執行1000次

for循環有2條基本語句，所以求和表達式（通項公式）是2，列式為

$\sum\limits_{i=0}^{999} 2$

根據求和式的上下限變換規則

$\sum\limits_{i=1}^{n} a_{i}=\sum\limits_{i=1+k}^{n+k} a_{i-k}$

本例的通項公式是常數2，沒有下標（或者說無論下標如何變化，通項不變）

$a_{1}=2,\ a_{2}=2,\ \cdots ,\ a_{n}=2$

所以只變換求和上下限

$\sum\limits_{i=0}^{999} 2=\sum\limits_{i=0+1}^{999+1} 2=\sum\limits_{i=1}^{1000} 2=\overbrace{2+\cdots + 2}^{1000} =2000$

在變換求和上下限后，也可根據求和式的數乘規則，提出常數再計算

$\sum\limits_{i=1}^{1000} 2=2\sum\limits_{i=1}^{1000} 1=2\times (\overbrace{1+\cdots + 1}^{1000}) = 2\times1000=2000$

算出語句頻度為2000（常數），數量級為 $1$ ，則時間復雜度為 $O( 1 )$

以后只要見到語句頻度是常數，不帶問題規模(n)，那么時間復雜度就是 $O( 1 )$

【例4.2】常數階? $O(1)$

int x=90,y=100; 
while(y>0)
{if(x>100) {x=x-10;y--;} else {x++;}
}

這道題挺唬人，一時間還不好算出來

但是如果你看出循環變量初始化和循環條件都是常數，不帶問題規模(n)

那么語句頻度肯定是常數，一秒即可得出時間復雜度為 $O(1)$

計算時間復雜度

1.基本語句：

x=x-10;

y--;

x++;

2.基本語句的語句頻度： $100\times(11+1)+1=100\times12+1=1201$

3.時間復雜度： $T(n)=O(1)$

如果仍要算出語句頻度，就得代入看邏輯了

【第1輪】

x==90，不滿足x>100，進else：x++（自增到91）

x==91，不滿足x>100，進else：x++（自增到92）

……

x==101，滿足x>100，進if：x=x-10（減到91）;? y--（自減到99）

? ?

【第2輪】

x==91，不滿足x>100，進else：x++（自增到92）

……

x==101，滿足x>100，進if：x=x-10（減到91）;? y--（自減到98）

? ??

【第3輪】

x==91，不滿足x>100，進else：x++（自增到92）

……

x==101，滿足x>100，進if：x=x-10（減到91）;? y--（自減到97）

? ? ?

……

? ? ?

【第100輪】

x==91，不滿足x>100，進else：x++（自增到92）

……

x==101，滿足x>100，進if：x=x-10（減到91）;? y--（自減到0）

? ??

以此類推，可以看到，除第1輪有x==90，其余輪次均是 x從91增到101，每輪循環執行11次

有人看到執行11次可能反應不過來，那就將91—101同時減90

相當于在數軸上將91—101整體向左移90個單位，得到1—11，這肯定是11次

注意，每輪最后x==101時，執行的不是else中的1條語句，而是if中的2條語句

所以每輪的語句頻度要比循環執行次數多1，即? $11+1=12$

語句頻度與循環執行次數不一定相等，因為循環體可以有多條語句

可以看到，每輪最后都會讓y自減：y--

因為while循環條件是 y>0，循環變量 y 能取的最小值（即求和下限）是1

所以 y從100減到1，循環共執行100輪

100輪，每輪執行11+1=12次，計算語句頻度

$100\times(11+1)=100\times12=1200$

看起來似乎是正確的，但是前面說了除第1輪有x==90，其余都沒有

所以還得把x==90時，多執行的1條語句：x++; 也算上，才是最終的語句頻度

$100\times(11+1)+1=100\times12+1=1201$

不過這只是探究罷了，實際上不需要算出語句頻度，只要看出是常數，時間復雜度就是 $O(1)$

? ??

（二）線性階??

【例5】線性階? $O(n)$

int n,i,t,a[100];
scanf("%d", &n);
for(i=0; i<n/2; i++) 
{ t=a[i]; a[i]=a[n-1-i]; a[n-1-i]=t; 
}

計算時間復雜度

1.基本語句：

t=a[i];?

a[i]=a[n-1-i];?

a[n-1-i]=t;

2.基本語句的語句頻度： $\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor } 3=\sum\limits_{i=1}^{\lfloor\frac{n-1}{2}\rfloor +1} 3=\overbrace{3+\cdots + 3}^{\lfloor\frac{n-1}{2}\rfloor+1} =3\times (\lfloor\frac{n-1}{2}\rfloor+1)$

3.時間復雜度： $T(n)=O(n)$

首先說明一下，? $\lfloor \ \rfloor$ ?這個符號代表向下取整

向下取整，如果不是整數，則只保留整數部分，忽略小數部分

向下取整，如果是整數，則仍是自身

$\lfloor 3.9 \rfloor=3$ ?，向下取整得 3

$\lfloor 16.183 \rfloor=16$ ?，向下取整得16

$\lfloor 7 \rfloor=7$ ?，整數向下取整，仍是自身

??

因為循環條件是 $i<\frac{n}{2}$

但n不確定是奇數還是偶數，所以? $\frac{n}{2}$ ?不能確定是小數還是整數

下面分情況討論

當n為奇數時，設 $n=2x+1$ （x是整數）

代入循環條件? $i<\frac{n}{2}$ ，得? $i<\frac{2x+1}{2}$ ，即? $i<x+\frac{1}{2}$

因為x是整數，所以整數 i 的最大值? $i_{max}=x$

前面設? $n=2x+1$ ，反之? $x=\frac{n-1}{2}$

將其代入? $i_{max}=x$ 得

奇數情況最大值? $i_{max}=x=\frac{n-1}{2}$

當n為偶數時，設 $n=2x$ （x是整數）

代入循環條件? $i<\frac{n}{2}$ ，得? $i<\frac{2x}{2}$ ，即? $i<x$

因為x是整數，所以整數 i 的最大值? $i_{max}=x-1$

前面設? $n=2x$ ，反之? $x=\frac{n}{2}$

將其代入? $i_{max}=x-1$ ?得

偶數情況最大值? $i_{max}=x-1=\frac{n}{2}-1$

兩種情況的最大值表達式不一樣，如何統一呢

前面提到的? $\lfloor \ \rfloor$ ?向下取整就派上用場了

先假設，最大值公式可用向下取整統一為，奇數情況最大值：? $i_{max}=\lfloor \frac{n-1}{2} \rfloor$

因為該式是從奇數情況推導出的，所以奇數肯定沒問題

代入驗證偶數情況，如果計算結果與偶數情況最大值相同，說明可以統一

當n為偶數時，設 $n=2x$ （x是整數）

代入上式得

$i_{max}=\lfloor \frac{n-1}{2} \rfloor=\lfloor \frac{2x-1}{2} \rfloor$

進一步化簡得

$i_{max} = \lfloor \frac{2x-1}{2} \rfloor \\[1.5ex] =\lfloor \frac{2x-1-1+1}{2} \rfloor \\[1.5ex] =\lfloor \frac{2x-2+1}{2} \rfloor \\[1.5ex] =\lfloor \frac{2(x-1)+1}{2} \rfloor \\[1.5ex] =\lfloor \frac{2(x-1)}{2} + \frac{1}{2} \rfloor\\[1.5ex]=\lfloor (x-1)+ \frac{1}{2} \rfloor \\[1.5ex] =x-1$

解釋一下，因為 $x$ ?是整數，所以? $x-1$ 也是整數

所以向下取整時，只保留整數部分： $x-1$ ，忽略小數部分：? $\frac{1}{2}$

前面設? $n=2x$ ，反之? $x=\frac{n}{2}$

將其代入得 $i_{max}=x-1=\frac{n}{2}-1$

將計算結果與偶數情況最大值? $i_{max}=\frac{n}{2}-1$ ?進行對照

可以看到，兩式均為? $\frac{n}{2}-1$ ，則偶數情況也成立，所以可以統一為? $i_{max}=\lfloor \frac{n-1}{2} \rfloor$

再假設，最大值公式可用向下取整統一為，偶數情況最大值：? $i_{max}=\lfloor \frac{n}{2}-1 \rfloor$

因為該式是從偶數情況推導出的，所以偶數肯定沒問題

代入驗證奇數情況，如果計算結果與奇數情況最大值相同，說明可以統一

當n為奇數時，設 $n=2x+1$ （x是整數）

代入上式得

$i_{max}=\lfloor \frac{n}{2}-1 \rfloor=\lfloor \frac{2x+1}{2}-1 \rfloor$

進一步化簡得

$i_{max}=\lfloor \frac{2x+1}{2}-1 \rfloor\\[1.5ex] =\lfloor \frac{2x+1}{2}-\frac{2}{2} \rfloor\\[1.5ex] =\lfloor \frac{2x+1-2}{2} \rfloor\\[1.5ex] =\lfloor \frac{2x-2+1}{2} \rfloor\\[1.5ex] =\lfloor \frac{2(x-1)+1}{2} \rfloor\\[1.5ex] =\lfloor \frac{2(x-1)}{2} + \frac{1}{2} \rfloor\\[1.5ex] =\lfloor (x-1)+\frac{1}{2} \rfloor\\[1.5ex] =x-1$

因為 $x$ ?是整數，所以? $x-1$ 也是整數

所以向下取整時，只保留整數部分： $x-1$ ，忽略小數部分：? $\frac{1}{2}$

前面設? $n=2x+1$ ，反之? $x=\frac{n-1}{2}$

將其代入得 $i_{max}=x-1=\frac{n-1}{2}-1$

將計算結果與奇數情況最大值? $i_{max}=\frac{n-1}{2}$ ?進行對照

可以看到，兩式一個為 $\frac{n-1}{2}-1$ ，另一個為 $\frac{n-1}{2}$ ，則奇數情況不成立，所以不能統一

將n=1到10的計算結果列成表格，也能看出本式不符合

最終統一為奇數情況最大值? $i_{max}=\lfloor \frac{n-1}{2} \rfloor$

所以 i 的最大值（求和上限）表示為? $\lfloor\frac{n-1}{2}\rfloor$ ?

循環變量 i 的變化區間是? $0\sim \lfloor\frac{n-1}{2}\rfloor$ ?

如果看不出執行次數，則同時+1

相當于在數軸上將? $0 \sim\lfloor\frac{n-1}{2}\rfloor$ 整體向右移1個單位，得? $1 \sim (\lfloor\frac{n-1}{2}\rfloor+1)$

則循環實際執行次數為? $\lfloor\frac{n-1}{2}\rfloor+1$ ?（這是因為 i 從0開始，所以執行次數要多1）

for循環有3條基本語句，所以求和表達式（通項公式）是3，列式為

$\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor} 3$

根據求和式的上下限變換規則

$\sum\limits_{i=1}^{n} a_{i}=\sum\limits_{i=1+k}^{n+k} a_{i-k}$

本例的通項公式是常數3，沒有下標，所以只變換求和上下限

$\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor} 3=\sum\limits_{i=0+1}^{\lfloor\frac{n-1}{2}\rfloor+1 } 3=\sum\limits_{i=1}^{\lfloor\frac{n-1}{2}\rfloor+1 } 3=\overbrace{3+\cdots + 3}^{\lfloor\frac{n-1}{2}\rfloor+1} =3\times (\lfloor\frac{n-1}{2}\rfloor+1)$

在變換求和上下限后，也可根據求和式的數乘規則，提出常數再計算

$\sum\limits_{i=1}^{\lfloor\frac{n-1}{2}\rfloor+1 } 3 =3\sum\limits_{i=1}^{\lfloor\frac{n-1}{2}\rfloor+1 } 1 =3\times (\overbrace{1+\cdots + 1}^{\lfloor\frac{n-1}{2}\rfloor+1}) =3\times (\lfloor\frac{n-1}{2}\rfloor+1)$

省略系數和無關項后，數量級為? $n$ ，則時間復雜度為? $O(n)$

（三）平方階

【例6.1】平方階? $O(n^{2})$

int n,i,j;
int a=0;
scanf("%d", &n);
for(i=0; i<n; i++)
{for(j=0; j<i; j++){a++;}
}

本例與【例3】嵌套相關循環略有不同，循環變量 i , j 不是從1開始，而是從0開始；循環條件不是<=，而是<

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\begin{matrix} \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{i-1} 1=\sum\limits_{i=0}^{n-1} \sum\limits_{j=1}^{i} 1=\sum\limits_{i=0}^{n-1} i=0+1+2+\cdots +(n-1)=\frac{n(n-1)}{2} \end{matrix}$

3.時間復雜度： $T(n)=O(n^{2})$

與【例3】嵌套相關循環同理，內外層循環相關，不能分開計算

因為外層循環條件是 i<n ，所以?i 能取的最大值（即求和上限）是：n-1

因為內層循環條件是 j<i ，所以?j?能取的最大值（即求和上限）是：i-1

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{i-1} 1$

雙重求和可以加括號以區分

$\sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{i-1} 1=\sum\limits_{i=0}^{n-1} (\sum\limits_{j=0}^{i-1} 1)$

可以類比復合函數，先計算括號內的

根據求和式上下限變換規則

$\sum\limits_{j=0}^{i-1} 1=\sum\limits_{j=0+1}^{i-1+1} 1=\sum\limits_{j=1}^{i} 1$

將其展開得

$\sum\limits_{j=1}^{i}1 =\overbrace{1+\cdots +1}^{i} = i$

將括號內的求和式替換為計算結果，雙重求和式變為??

$\sum\limits_{i=0}^{n-1} (\sum\limits_{j=0}^{i-1} 1)=\sum\limits_{i=0}^{n-1} i$

這里比較特殊，通項公式就是求和變量：? $a_{i}=i$

$\sum\limits_{i=0}^{n-1} i=0+1+2+\cdots +(n-1)$

求和變量 i 從 0?到 n-1，則通項公式也是從 0?到 n-1，求和式整體即從0累加到n-1

此時變為等差數列求和，代入等差數列求和公式?

$S_{n}=\frac{n(a_{1}+a_{n})}{2}$ ?

得到語句頻度

$\sum\limits_{i=0}^{n-1} i=0+1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$

將其展開得

$\frac{n(n-1)}{2}=\frac{1}{2}n^{2}-\frac{1}{2}n$

除了上述解法，其實還可以使用求和式的上下限變換規則

求和上下限變換（+1），通項下標也對應變換（-1）

這里比較特殊，因為通項公式? $a_{i}=i$ ?，所以變換為? $a_{i-1}=i-1$

$\sum\limits_{i=0}^{n-1} i =\sum\limits_{i=0+1}^{n-1+1} (i-1) =\sum\limits_{i=1}^{n} (i-1)$

再使用求和式的加法規則（減法同理）進行拆分

$\sum\limits_{i=1}^{n} (i-1) =\sum\limits_{i=1}^{n} i-\sum\limits_{i=1}^{n} 1$

同樣可以得到語句頻度

$\sum\limits_{i=1}^{n} i-\sum\limits_{i=1}^{n} 1=\frac{n(n+1)}{2}-n=\frac{n^{2}+n-2n}{2}=\frac{n^{2}-n}{2}=\frac{n(n-1)}{2}$

將其展開得

$\frac{n(n-1)}{2}=\frac{1}{2}n^{2}-\frac{1}{2}n$

省略系數和無關項后，數量級為? $n^{2}$ ，則時間復雜度為? $O(n^{2})$

【例6.2】平方階? $O(n^{2})$ ?——冒泡排序（最壞情況）

int n,i,j,t,a[100];
scanf("%d", &n);
for(i=0; i<n; i++)
{scanf("%d", &a[i]);
}
for(i=0; i<n-1; i++)
{for(j=0; j<n-1-i; j++){if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}}
}
for(i=0; i<n; i++)
{printf("%d ", a[i]);
}

計算時間復雜度

1.基本語句：

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

2.基本語句的語句頻度：

$\begin{matrix} \sum\limits_{i=0}^{n-2} \sum\limits_{j=0}^{n-2-i} 3=\sum\limits_{i=0}^{n-2} \sum\limits_{j=1}^{n-1-i} 3= \sum\limits_{i=0}^{n-2}3 (n-1-i)= 3\sum\limits_{i=0}^{n-2} (n-1-i)=3[\sum\limits_{i=0}^{n-2} (n-1)-\sum\limits_{i=0}^{n-2} i]=\frac{3}{2}n(n-1) \end{matrix}$

3.時間復雜度： $T(n)=O(n^{2})$

代碼中有三個for循環

第1個是一層for循環，輸入數據，執行n次

第2個是二層for循環，冒泡排序，外層循環執行n-1次，且內層循環次數與 i 相關，所以執行次數肯定>n

第3個是一層for循環，輸出數據，執行n次

假設當前冒泡排序為最壞情況（逆序），每次循環都會交換變量

所以基本語句是二層for循環體中的3條交換語句，則求和表達式（通項公式）是 3

基本語句所在的二層for循環是嵌套相關循環，內外層循環相關，不能分開計算

因為外層循環條件是 i<n-1 ，所以?i 能取的最大值（即求和上限）是：(n-1)-1=n-2

因為內層循環條件是 j<n-1-i ，所以?j?能取的最大值（即求和上限）是：(n-1-i)-1=n-2-i

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{i=0}^{n-2} \sum\limits_{j=0}^{n-2-i} 3$

雙重求和可以加括號以區分

$\sum\limits_{i=0}^{n-2} \sum\limits_{j=0}^{n-2-i} 3=\sum\limits_{i=0}^{n-2} (\sum\limits_{j=0}^{n-2-i} 3)$

可以類比復合函數，先計算括號內的

根據求和式的上下限變換規則

$\sum\limits_{j=0}^{n-2-i} 3=\sum\limits_{j=0+1}^{n-2-i+1} 3=\sum\limits_{j=1}^{n-1-i} 3$

將其展開得

$\sum\limits_{j=1}^{n-1-i} 3 =\overbrace{3+\cdots+3}^{n-1-i} =3(n-1-i)$

（這里只不過是把求和上限變成 n-1-i，與前面本質相同，就是 n-1-i?個1相加）

將括號內的求和式替換為計算結果，雙重求和變為??

$\sum\limits_{i=0}^{n-2} (\sum\limits_{j=0}^{n-2-i} 3)=\sum\limits_{i=0}^{n-2} [3(n-1-i)]$

根據求和式的數乘規則，將常數提出

$\sum\limits_{i=0}^{n-2} [3(n-1-i)]=3\sum\limits_{i=0}^{n-2} (n-1-i)$

根據求和式的加法規則（減法同理），進行拆分

$3\sum\limits_{i=0}^{n-2} (n-1-i)=3[\sum\limits_{i=0}^{n-2} (n-1)-\sum\limits_{i=0}^{n-2} i]$

將兩個求和式分別計算：

第一個求和式

根據求和式的上下限變換規則，通項公式(n-1)與求和變量 i 無關，可以看作常數，所以只變換求和上下限

$\sum\limits_{i=0}^{n-2} (n-1) =\sum\limits_{i=0+1}^{n-2+1} (n-1)=\sum\limits_{i=1}^{n-1} (n-1)$

將其展開得

$\sum\limits_{i=1}^{n-1} (n-1)=\overbrace{(n-1)+\cdots+(n-1)}^{n-1}=(n-1)(n-1)$

第二個求和式

將其展開得

$\sum\limits_{i=0}^{n-2} i=0+\cdots+(n-2)=\frac{(n-1)(0+n-2)}{2}=\frac{(n-1)(n-2)}{2}$

將兩式結果代入得到語句頻度

$3[\sum\limits_{i=1}^{n-1} (n-1)-\sum\limits_{i=0}^{n-2} i]\\[1.5ex] =3[(n-1)(n-1)-\frac{(n-1)(n-2)}{2}]\\[1.5ex] =\frac{3}{2}[2(n-1)(n-1)-(n-1)(n-2)]\\[1.5ex] =\frac{3}{2}(n-1)[2(n-1)-(n-2)]\\[1.5ex] =\frac{3}{2}(n-1)(2n-2-n+2)\\[1.5ex] =\frac{3}{2}(n-1)n\\[1.5ex] =\frac{3}{2}n(n-1)$

將其展開得

$\frac{3}{2}n(n-1)=\frac{3}{2}n^{2}-\frac{3}{2}n$

省略系數和無關項后，數量級為? $n^{2}$ ，則時間復雜度為? $O(n^{2})$

【例6.3】 $O(n\times m)$

int n,m,i,j,a[10][10];
scanf("%d%d", &n, &m);
for(i=0; i<n; i++)
{for(j=0; j<m; j++) {a[i][j]=i*m+j;}
}

注意，本例的問題規模由n和m共同決定

計算時間復雜度

1.基本語句：a[i][j]=i*m+j;

2.基本語句的語句頻度： $\Large \sum\limits_{i=0}^{n-1}1 \times \sum\limits_{j=0}^{m-1}1=\Large \sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{m}1=n \times m$

3.時間復雜度： $T(n)=O(n\times m )$

嵌套無關循環，所以內外層循環互不干擾，語句頻度獨立計算

因為外層循環條件是 i<n?，所以?i 能取的最大值（即求和上限）是：n-1

而內層循環可以看作是外層循環體的1條基本語句，則求和表達式（通項公式）是1

所以外層循環的語句頻度為（上下限變換規則）

$\sum\limits_{i=0}^{n-1}1=\sum\limits_{i=0+1}^{n-1+1}1=\sum\limits_{i=1}^{n}1 = n$

因為內層循環條件是 j<m?，所以?j?能取的最大值（即求和上限）是：m-1

內層循環體只有1條基本語句：a[i][j]=i*m+j;? 則求和表達式（通項公式）是1

所以內層循環的語句頻度為（上下限變換規則）

$\sum\limits_{j=0}^{m-1}1=\sum\limits_{j=0+1}^{m-1+1}1=\sum\limits_{j=1}^{m}1 = m$

只有當內外層循環都結束時，算法才結束

（即算法結束需要分內層循環、外層兩循環個步驟）

根據統計學的乘法原理，需要把二者相乘得語句頻度

$\Large \sum\limits_{i=0}^{n-1}1 \times \sum\limits_{j=0}^{m-1}1=\Large \sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{m}1=n \times m$

因為問題規模由n和m共同決定，不能合并，所以數量級為? $n\times m$ ，時間復雜度為? $O(n\times m)$

? ??

（四）立方階

【例7.1】立方階? $O(n^{3})$ ?

int n,i,j,k,a=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{for(j=1; j<=n; j++){for(k=1; k<=j; k++){a++;}}
}

可以看到，第二層循環條件是 j<=n，與第一層循環變量 i 無關，j 從1到 n，執行 n?次

無論第一層循環變量 i 取何值，第二層循環都會執行n次

???

可以看到，第三層循環條件是 k<=j，與第二層循環變量 j 相關，k?從1到 j，執行 j?次

當第二層循環變量 j?的值發生改變時，第三層循環的執行次數也會隨之改變

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n} \sum\limits_{k=1}^{j} 1 =n \times \sum\limits_{j=1}^{n}j =n \times \frac{n(n+1)}{2} =\frac{n^{2}(n+1)}{2}$

3.時間復雜度： $T(n)=O(n^{3})$

第一層是嵌套無關循環，語句頻度獨立計算

因為第一層循環條件是 i<=n ，所以?i 能取的最大值（即求和上限）是：n

內層循環可以看作是外層循環體的1條基本語句，所以求和表達式（通項公式）是1

所以第一層循環的求和式為

$\sum\limits_{i=1}^{n}1=\overbrace{1+\cdots +1}^{n}=n$

第二、三層是嵌套相關循環，不能分開計算

因為第二層循環條件是 j<=n ，所以 j 能取的最大值（即求和上限）是：n

因為第三層循環條件是 k<=j ，所以 k 能取的最大值（即求和上限）是：j

內層循環體只有1條基本語句，所以求和表達式（通項公式）是1

所以第二、三層循環的求和式為

$\sum\limits_{j=1}^{n} \sum\limits_{k=1}^{j} 1$

雙重求和可以加括號以區分

$\sum\limits_{j=1}^{n} \sum\limits_{k=1}^{j} 1 =\sum\limits_{j=1}^{n} (\sum\limits_{k=1}^{j} 1)$

可以類比復合函數，先計算括號內的

$\sum\limits_{k=1}^{j}1 =\overbrace{1+\cdots +1}^{j} = j$

將括號內的求和式替換為計算結果

$\sum\limits_{j=1}^{n} (\sum\limits_{k=1}^{j} 1)=\sum\limits_{j=1}^{n} j$

將其展開得到

$\sum\limits_{j=1}^{n}j =1+\cdots +n$

這里比較特殊，通項公式就是求和變量：? $a_{j}=j$

求和變量 j?從 1 到 n，則通項公式也是從 1 到 n，求和式整體即從1累加到 n

此時變為等差數列求和，代入等差數列求和公式?

$S_{n}=\frac{n(a_{1}+a_{n})}{2}$ ?

得到

$\sum \limits_{j=1}^{n}j =1+\cdots +n = \frac{n(n+1)}{2}$

??

只有當第一層和第二、三層循環都結束時，算法才結束

（即算法結束需要分第一層循環和第二、三層循環兩個步驟）

根據統計學的乘法原理，需要把二者相乘得語句頻度

$\sum\limits_{i=1}^{n}1 \times \sum\limits_{j=1}^{n} \sum\limits_{k=1}^{j} 1\\[1.5ex] =n \times \sum\limits_{j=1}^{n} (\sum\limits_{k=1}^{j} 1)\\[1.5ex] =n \times \sum\limits_{j=1}^{n}j\\[1.5ex] =n \times \frac{n(n+1)}{2}\\[1.5ex] =\frac{n^{2}(n+1)}{2}$

將其展開得

$\frac{n^{2}(n+1)}{2}=\frac{1}{2}n^{3} + \frac{1}{2}n^2$

省略系數和無關項后，數量級為? $n^{3}$ ，則時間復雜度為? $O(n^{3})$

【例7.2】立方階? $O(n^{3})$ ?

int n,i,j,k,a=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{for(j=1; j<=i; j++){for(k=1; k<=j; k++){a++;}}
}

可以看到，第二層循環條件是 j<=i，與第一層循環變量 i 相關，j 從1到 i，執行 i 次

當第一層循環變量 i 的值發生改變時，第二層循環的執行次數也會隨之改變

???

可以看到，第三層循環條件是 k<=j，與第二層循環變量 j 相關，k?從1到 j，執行 j?次

當第二層循環變量 j?的值發生改變時，第三層循環的執行次數也會隨之改變

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=1}^{j} 1 =\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} j =\sum\limits_{i=1}^{n} (\frac{i^{2}+i}{2}) = \frac{\sum\limits_{i=1}^{n}i^{2}+\sum\limits_{i=1}^{n}i}{2} = \frac{n(n+1)(n+2)}{6}$

3.時間復雜度： $T(n)=O(n^{3})$

嵌套相關循環，一、二、三層循環相關，不能分開計算

因為第一層循環條件是 i<=n ，所以?i 能取的最大值（即求和上限）是：n

因為第二層循環條件是 j<=i ，所以 j 能取的最大值（即求和上限）是：i

因為第三層循環條件是 k<=j ，所以 k 能取的最大值（即求和上限）是：j

第三層循環體只有1條基本語句，所以求和表達式（通項公式）是1

三層循環（三重循環）計算語句頻度需要寫成三重求和

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=1}^{j} 1$

三重求和可以加括號以區分

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=1}^{j} 1 =\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} (\sum\limits_{k=1}^{j} 1)$ ?

可以類比復合函數，先計算括號內的

$\sum\limits_{k=1}^{j}1 =\overbrace{1+\cdots +1}^{j} = j$

將括號內的求和式替換為計算結果，三重求和變為雙重求和??

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} (\sum\limits_{k=1}^{j} 1)= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} j$

雙重求和也可以加括號以區分

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} j =\sum\limits_{i=1}^{n} (\sum\limits_{j=1}^{i} j)$

可以類比復合函數，先計算括號內的

$\sum\limits_{j=1}^{i}j =1+\cdots +i$

這里比較特殊，通項公式就是求和變量：? $a_{j}=j$

求和變量 j?從 1 到 i，則通項公式也是從 1 到 i，求和式整體即從1累加到 i

此時變為等差數列求和，代入等差數列求和公式?

$S_{n}=\frac{n(a_{1}+a_{n})}{2}$ ?

得到

$\sum\limits_{j=1}^{i}j =1+\cdots +i = \frac{i(i+1)}{2}$

將括號內的求和式替換為計算結果，雙重求和變為

$\sum\limits_{i=1}^{n} (\sum\limits_{j=1}^{i} j) =\sum\limits_{i=1}^{n} [\frac{i(i+1)}{2}]$

將分子展開得

$\sum\limits_{i=1}^{n} [\frac{i(i+1)}{2}] =\sum\limits_{i=1}^{n} (\frac{i^{2}+i}{2})$

根據求和式的線性規則（數乘規則、加法規則）

對多項式求和就是對其中每一項分別應用求和運算

$\sum\limits_{i=1}^{n} (\frac{i^{2}+i}{2}) = \frac{\sum\limits_{i=1}^{n}i^{2}+\sum\limits_{i=1}^{n}i}{2}$

這兩個求和式的值都是已知的

第一個求和式

$\sum\limits_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}$

如果想了解如何推導出? $i^{2}$ ?求和的值，可以看我的這篇文章：《求和式及其運算規則》

第二個求和式

$\sum\limits_{i=1}^{n}i=1+\cdots +n=\frac{n(n+1)}{2}$

將兩式結果代入得到語句頻度

$\frac{\sum\limits_{i=1}^{n}i^{2}+\sum\limits_{i=1}^{n}i}{2} \\[1.5ex] = \frac{\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}}{2} \\[1.5ex] = \frac{1}{2} [\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}]\\[1.5ex] = \frac{1}{2} [\frac{n(n+1)(2n+1)}{6}+\frac{3n(n+1)}{6}]\\[1.5ex] = \frac{1}{2} [\frac{n(n+1)(2n+1+3)}{6}] \\[1.5ex] = \frac{1}{2} [\frac{n(n+1)(2n+4)}{6}] \\[1.5ex] = \frac{1}{2} [\frac{n(n+1)2(n+2)}{6}] \\[1.5ex] = \frac{n(n+1)(n+2)}{6}$

將其展開得

$\frac{n(n+1)(n+2)}{6}=\frac{1}{6}n^{3} + \frac{1}{2}n^2 +\frac{1}{3}n$

省略系數和無關項后，數量級為? $n^{3}$ ，則時間復雜度為? $O(n^{3})$

（五）對數階

【例8.1】對數階? $O(log_{2}n)$ ?

int n,i,a=0;
scanf("%d", &n);
for(i=1; i<=n; i*=2)
{a++;
}

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor log_{2}{(n)}+1\rfloor}=\lfloor log_{2}{(n)}+1\rfloor$

3.時間復雜度： $T(n)=O(log_{2}{n})$

因為本例的循環變量自增不是以往的 i++，而是 i*=2

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 i 的變化規律，將其當作數列

循環變量初始化：i=1，則首項? $a_{1}=1$

循環變量自增：i*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 i 隨著通項公式改變?

$i=a_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] i=a_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] i=a_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] i=a_{x}=2^{x-1} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i=2^{x-1}$

（注：此處及后續提到的 "最后一次循環" 均是指能進循環體的 "最后一次循環"）

又因為循環條件是 $i \leqslant n$

所以最后一次循環時 $i=n$ ，則

$i=2^{x-1}= n$

等式兩邊同時取對數

$x-1=log_{2}{(n)}$

移項，得到循環執行次數x的值

$x=log_{2}{(n)}+1$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor log_{2}{(n)}+1\rfloor$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor log_{2}{(n)}+1\rfloor$ ，代表循環執行? $\lfloor log_{2}{(n)}+1\rfloor$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor log_{2}{(n)}+1\rfloor}=\lfloor log_{2}{(n)}+1\rfloor$

省略系數和無關項后，數量級為? $log_{2}{n}$ ，則時間復雜度為? $O(log_{2}{n})$

【例8.2】對數階? $O(log_{2}n)$ ?

int n,i,a=0;
scanf("%d", &n);
for(i=2; i<n; i*=2)
{a++;
}

本例是對【例8.1】稍作修改，循環變量初始化：i=2，循環條件：i<n

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lceil log_{2}(n) \rceil-1} 1=\overbrace{1+\cdots +1}^{\lceil log_{2}(n) \rceil-1}=\lceil log_{2}(n) \rceil-1$

3.時間復雜度： $T(n)=O(log_{2}{n})$

因為本例的循環變量自增不是以往的 i++，而是 i*=2

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 i 的變化規律，將其當作數列

循環變量初始化：i=2，則首項? $a_{1}=2$

循環變量自增：i*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=2\times 2^{n-1}=2^{n}$

則循環變量 i 隨著通項公式改變?

$i=a_{1}=2^{1} \\[1.5ex] i=a_{2}=2^{2} \\[1.5ex] i=a_{3}=2^{3} \\[1.5ex] \cdots \\[1.5ex] i=a_{x}=2^{x}$

所以最后一次循環（第x次循環）時

$i=2^{x}$

又因為循環條件是 $i<n$

不等式兩邊不都是整數表達式，不好計算最后一次循環的x值

所以不追求列等式，而是直接將? $i=2^{x}$ ?代入不等式，得

$i=2^{x}<n$

不等式兩邊同時取對數，得到循環執行次數x的范圍

$x<log_{2}(n)$

但是循環執行次數只能是整數，所以x的最大值是

$x_{max}=\lceil log_{2}(n) \rceil-1$

到這你肯定很疑惑，這個最大值是怎么來的

首先說明一下，? $\lceil \ \rceil$ ?這個符號代表向上取整

向上取整，如果不是整數，則讓整數部分加1，忽略小數部分

向上取整，如果是整數，則仍是自身

$\lceil 3.9 \rceil=4$ ?，向上取整得 4

$\lceil 16.183 \rceil=17$ ?，向上取整得17

$\lceil 7 \rceil=7$ ?，整數向上取整，仍是自身

? ??

下面解釋最大值如何得出

將對數? $log_{2}(n)$ ?作為一個整體

設其整數部分為m，小數部分為f，則?

$log_{2}(n)=m+f$ ??

當小數部分不存在時（即 $f=0$ ），則? $m+f=m+0=m$

因為 $log_{2}(n)=m+f$ ，將對數整體代換得 $log_{2}(n)=m$

前面已推導出x的范圍為? $x<log_{2}(n)$ ，將上式代入得? $x<m$

此時不等式兩邊都是整數，所以當小數部分不存在時，x的最大值? $x_{max}=m-1$

當小數部分存在時（即 $0<f<1$ ），則? $m<(m+f)<(m+1)$

因為 $log_{2}(n)=m+f$ ，將對數整體代換得 $m<log_{2}(n)<(m+1)$

前面已推導出x的范圍為? $x<log_{2}(n)$ ，不等式放縮得? $x<(m+1)$

此時不等式兩邊都是整數，所以當小數部分存在時，x的最大值? $x_{max}=(m+1)-1=m$

可以用? $\lceil \ \rceil$ ?向上取整將兩種情況統一起來

當小數部分不存在時（即 $f=0$ ），前面整體代換已得? $log_{2}(n)=m$

m是整數，所以向上取整后仍為m，即? $\lceil log_{2}(n)\rceil=m$

代入小數部分不存在時，x的最大值? $x_{max}=m-1=\lceil log_{2}(n)\rceil-1$

當小數部分存在時（即 $0<f<1$ ），前面整體代換已得? $m<log_{2}(n)<(m+1)$

m是整數，則m+1也是整數，所以向上取整后為m+1，即? $\lceil log_{2}(n)\rceil=m+1$

代入小數部分存在時，x的最大值? $x_{max}=m=(m+1)-1=\lceil log_{2}(n)\rceil-1$

所以最終統一為

$x_{max}=\lceil log_{2}(n) \rceil-1$

如果設? $f(n)=log_{2}(n)$ ，可得出以下結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

這個可以作為普遍結論，因為推導的全程都是把? $log_{2}(n)$ ?當作一個整體

順便提一下，這個結論對于【例5】線性階同樣適用

再把【例5】的代碼貼過來

int n,i,t,a[100];
scanf("%d", &n);
for(i=0; i<n/2; i++) 
{ t=a[i]; a[i]=a[n-1-i]; a[n-1-i]=t; 
}

根據上面的結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

代入【例5】：

i 是整數，不等式關系為? $i<\frac{n}{2}$ ，則整數 i 的最大值? $i_{max}=\lceil \frac{n}{2} \rceil-1$

所以【例5】的語句頻度也可以表示為

$\sum\limits_{i=0}^{\lceil \frac{n}{2} \rceil-1} 3 =\sum\limits_{i=0+1}^{\lceil \frac{n}{2} \rceil-1 +1} 3 =\sum\limits_{i=1}^{\lceil \frac{n}{2} \rceil} 3 =\overbrace{3+\cdots + 3}^{\lceil \frac{n}{2} \rceil} =3\times \lceil \frac{n}{2} \rceil$

省略系數后，數量級為 $n$ ，所以時間復雜度仍為 $O(n)$

??

將n=1到10的計算結果列成表格，也能看出本式是符合的

回到本題，現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lceil log_{2}(n) \rceil-1$ ，代表循環執行? $\lceil log_{2}(n) \rceil-1$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lceil log_{2}(n) \rceil-1} 1=\overbrace{1+\cdots +1}^{\lceil log_{2}(n) \rceil-1}=\lceil log_{2}(n) \rceil-1$

省略系數和無關項后，數量級為? $log_{2}{n}$ ，則時間復雜度為? $O(log_{2}{n})$

【例8.3】對數階? $O(log_{3}{n})=O(log_{2}{n})=O(log\,{n})$

int n,i,a=0;
scanf("%d", &n);
for(i=2; i<=n; i*=3)
{a++;
}

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor}=\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor$

3.時間復雜度： $T(n)=O(log_{3}{n})=O(log_{2}{n})=O(log\,{n})$

? ?

因為本例的循環變量自增不是以往的 i++，而是 i*=3

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 i 的變化規律，將其當作數列

循環變量初始化：i=2，則首項? $a_{1}=2$

循環變量自增：i*=3，則公比? $q=3$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=2\times 3^{n-1}$

則循環變量 i 隨著通項公式改變?

$i=a_{1}=2\times 3^{1-1}=2\times 3^{0}=2\times 1=2 \\[1.5ex] i=a_{2}=2\times 3^{2-1}=2\times 3^{1}=2\times 3=6 \\[1.5ex] i=a_{3}=2\times 3^{3-1}=2\times 3^{2}=2\times 9=18 \\[1.5ex] \cdots \\[1.5ex] i=a_{x}=2\times 3^{x-1}$

所以最后一次循環（第x次循環）時

$i=a_{x}=2\times 3^{x-1}$

又因為循環條件是 $i \leqslant n$

所以最后一次循環時 $i=n$ ，則

$i=2\times 3^{x-1} = n$

等式兩邊同時除以2

$3^{x-1} = \frac{n}{2}$

等式兩邊同時取對數

$x-1=log_{3}{(\frac{n}{2})}$

根據對數的減法法則

$log_{a}{(\frac{M}{N})}=log_{a}{(M)}-log_{a}{(N)}$

等式右邊可以拆分為

$log_{3}{(\frac{n}{2})}=log_{3}{(n)}-log_{3}{(2)}$

代入原式得

$x-1=log_{3}{(n)}-log_{3}{(2)}$

移項，得到循環執行次數x的值

$x=log_{3}{(n)}-log_{3}{(2)}+1$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor$ ，代表循環執行? $\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor}=\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor$

其中? $log_{3}{(2)}$ ?是常數

省略系數和無關項后，數量級為? $log_{3}{n}$ ，則時間復雜度為? $O(log_{3}{n})$

或根據對數的換底公式

$log_{a}{(b)}=\frac{log_{c}{(b)}}{log_{c}{(a)}}$

上面的對數可以改寫為

$log_{3}{(n)}=\frac{log_{2}{(n)}}{log_{2}{(3)}}=\frac{1}{log_{2}{(3)}}log_{2}{(n)}$

$log_{3}{(2)}=\frac{log_{2}{(2)}}{log_{2}{(3)}}=\frac{1}{log_{2}{(3)}}$

則語句頻度改寫為

$\lfloor log_{3}{(n)}-log_{3}{(2)}+1 \rfloor=\lfloor \frac{1}{log_{2}{(3)}}log_{2}{(n)}-\frac{1}{log_{2}{(3)}}+1 \rfloor$ ??

其中 $\frac{1}{log_{2}{(3)}}$ 是常數

省略系數和無關項后，數量級為? $log_{2}{n}$ ，則時間復雜度為? $O(log_{2}{n})$

???

因為可以換底，所以任意底數(k)的對數都可以轉化為 "常數 × 底數為2的對數"

$log_{k}(n)=\frac{log_{2}(n)}{log_{2}(k)}=\frac{1}{log_{2}(k)}log_{2}(n)$

（注：n是自變量，k是常數）

因為計算時間復雜度會省略系數，所以對數階的時間復雜度均相同（即底數可以省略）

$O(log_{k}{n})=O(log_{2}{n})=O(log\,{n})$

（六）線性對數階

【例9】線性對數階? $O(nlog_{2}n)=O(nlog\,n)$ ?

int n,i,j,a=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
{for(j=1; j<=n; j*=2){a++;}
}

本例其實就是將【例2】嵌套無關循環和【例8.1】對數階結合起來

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{i=1}^{n}1 \times \sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1=n\times \lfloor log_{2}{(n)}+1\rfloor$

3.時間復雜度： $T(n)=O(nlog_{2}{n})=O(nlog\,n)$

嵌套無關循環，所以內外層循環互不干擾，語句頻度獨立計算

因為外層循環條件是 i<=n?，所以?i 能取的最大值（即求和上限）是：n

而內層循環可以看作是外層循環體的1條基本語句，則求和表達式（通項公式）是1

所以外層循環的語句頻度為

$\sum\limits_{i=1}^{n}1 =\overbrace{1+\cdots +1}^{n} = n$

因為內層循環變量自增不是以往的 j++，而是 j*=2

所以循環變量 j?不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 j?的變化規律，將其當作數列

循環變量初始化：j=1，則首項? $a_{1}=1$

循環變量自增：j*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 j?隨著通項公式改變?

$j=a_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] j=a_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] j=a_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] j=a_{x}=2^{x-1} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$j=2^{x-1}$

又因為循環條件是 $j \leqslant n$

所以最后一次循環時 $j=n$ ，則

$j=2^{x-1}= n$

等式兩邊同時取對數所以求和

$x-1=log_{2}{(n)}$

移項，得到循環執行次數x的值

$x=log_{2}{(n)}+1$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor log_{2}{(n)}+1\rfloor$

現在就可以列求和式計算了

內層循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor log_{2}{(n)}+1\rfloor$ ，代表循環執行? $\lfloor log_{2}{(n)}+1\rfloor$ 次

所以內層循環的語句頻度為：

$\sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor log_{2}{(n)}+1\rfloor}=\lfloor log_{2}{(n)}+1\rfloor$

根據統計學乘法原理，兩式相乘得

$\sum\limits_{i=1}^{n}1 \times \sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1=n\times \lfloor log_{2}{(n)}+1\rfloor$

省略系數和無關項后，數量級為? $nlog_{2}{n}$ ，則時間復雜度為? $O(nlog_{2}{n})=O(nlog\,{n})$

（七）根號階

【例10.1】根號階? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

int n,i,a=0;
scanf("%d", &n);
for(i=1; i*i<=n; i++)
{a++;
}

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{n} \rfloor}=\lfloor \sqrt{n} \rfloor$

3.時間復雜度： $T(n)=O(\sqrt{n})=O(n^{\frac{1}{2}})$

?

因為本例的循環條件不是以往的 i<=n，而是 i*i<=n

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環條件?i*i 的變化規律，將其當作數列

循環變量初始化：i=1

循環變量自增：i++

將循環變量 i 的值依次代入循環條件 i*i，探尋數列規律

$i*i=a_{1}=1\times 1=1^{2} \\[1.5ex] i*i=a_{2}=2\times 2=2^{2} \\[1.5ex] i*i=a_{3}=3\times 3=3^{2} \\[1.5ex] \cdots \\[1.5ex] i*i=a_{x}=x\times x=x^{2} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i*i=x^{2}$

又因為循環條件是 $i*i\leqslant n$

所以最后一次循環時 $i*i=n$ ，則

$i*i=x^{2}= n$

等式兩邊同時開平方，得到循環執行次數x的值

$x=\sqrt{n}$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor \sqrt{n} \rfloor$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor \sqrt{n} \rfloor$ ，代表循環執行? $\lfloor \sqrt{n} \rfloor$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{n} \rfloor}=\lfloor \sqrt{n} \rfloor$

省略系數和無關項后，數量級為? $\sqrt{n}$ ，則時間復雜度為? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

【例10.2】根號階? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

int n,i,a=0;
scanf("%d", &n);
for(i=2; i*i<n; i++)
{a++;
}

本例是對【例10.1】稍作修改，循環變量初始化：i=2，循環條件：i*i<n

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil-2} 1=\overbrace{1+\cdots +1}^{\lceil \sqrt{n}\ \rceil-2}=\lceil \sqrt{n}\ \rceil-2$

3.時間復雜度： $T(n)=O(\sqrt{n})=O(n^{\frac{1}{2}})$

?

因為本例的循環條件不是以往的 i<n，而是 i*i<n

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環條件?i*i 的變化規律，將其當作數列

循環變量初始化：i=2

循環變量自增：i++

將循環變量 i 的值依次代入循環條件 i*i，探尋數列規律

$i*i=a_{1}=2\times 2=2^{2} \\[1.5ex] i*i=a_{2}=3\times 3=3^{2} \\[1.5ex] i*i=a_{3}=4\times 4=4^{2} \\[1.5ex] \cdots \\[1.5ex] i*i=a_{x}=(x+1)\times (x+1)=(x+1)^{2} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i*i=(x+1)^{2}$

又因為循環條件是 $i*i < n$

不等式兩邊不都是整數表達式，不好計算最后一次循環的x值

所以不追求列等式，而是直接將? $i*i=(x+1)^{2}$ ?代入不等式，得

$i*i=(x+1)^{2}<n$

不等式兩邊同時開平方

$x+1<\sqrt{n}$

移項，得到循環執行次數x的范圍

$x<\sqrt{n}-1$

根據【例8.2】中的結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

代入本題：

x是整數，不等式關系為? $x<\sqrt{n}-1$ ?，則整數x的最大值? $x_{max}=\lceil \sqrt{n}-1 \rceil-1=\lceil \sqrt{n}\ \rceil-2$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lceil \sqrt{n}\ \rceil-2$ ，代表循環執行? $\lceil \sqrt{n}\ \rceil-2$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil-2} 1=\overbrace{1+\cdots +1}^{\lceil \sqrt{n}\ \rceil-2}=\lceil \sqrt{n}\ \rceil-2$

省略系數和無關項后，數量級為? $\sqrt{n}$ ，則時間復雜度為? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

【例10.3】根號階? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

int n,i,a=0;
scanf("%d", &n);
for(i=1; i<=sqrt(n); i++)
{a++;
}

本例與【例10.1】如出一轍

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{i=1}^{\lfloor \sqrt{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{n} \rfloor}=\lfloor \sqrt{n} \rfloor$

3.時間復雜度： $T(n)=O(\sqrt{n})=O(n^{\frac{1}{2}})$

?

本例的循環條件不是以往的 i<=n，而是 i<=sqrt(n)

sqrt是平方根( square root )的縮寫，sqrt(n)即為 $\sqrt{n}$

所以循環條件可寫為? $i\leqslant \sqrt{n}$

按理說 i 能取的最大值應該是 $\sqrt{n}$

但是 $\sqrt{n}$ ?不一定是整數，所以需要向下取整? $\lfloor \sqrt{n} \rfloor$

則最后一次循環時 $i=\lfloor \sqrt{n} \rfloor$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

則語句頻度為：

$\sum\limits_{i=1}^{\lfloor \sqrt{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{n} \rfloor}=\lfloor \sqrt{n} \rfloor$

省略系數和無關項后，數量級為? $\sqrt{n}$ ，則時間復雜度為? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

【例10.4】根號階? $O(\sqrt[3]{n})=O(n^{\frac{1}{3}})$

int n,i,a=0;
scanf("%d", &n);
for(i=1; i*i*i<=n; i++)
{a++;
}

計算時間復雜度

1.基本語句：a++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lfloor \sqrt[3]{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt[3]{n} \rfloor}=\lfloor \sqrt[3]{n} \rfloor$

3.時間復雜度： $T(n)=O(\sqrt[3]{n})=O(n^{\frac{1}{3}})$

?

因為本例的循環條件不是以往的 i<=n，而是 iii<=n

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環條件?iii 的變化規律，將其當作數列

循環變量初始化：i=1

循環變量自增：i++

將循環變量 i 的值依次代入循環條件 iii，探尋數列規律

$i*i*i=a_{1}=1\times 1\times 1=1^{3} \\[1.5ex] i*i*i=a_{2}=2\times 2\times 2=2^{3} \\[1.5ex] i*i*i=a_{3}=3\times 3\times 3=3^{3} \\[1.5ex] \cdots \\[1.5ex] i*i*i=a_{x}=x\times x\times x=x^{3}\\[1.5ex]$

所以最后一次循環（第x次循環）時

$i*i*i=x^{3}$

又因為循環條件是 $iii \leqslant n$

所以最后一次循環時 $iii=n$ ，則

$i*i*i=x^{3}= n$

等式兩邊同時開立方，得到循環執行次數x的值

$x=\sqrt[3]{n}$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor \sqrt[3]{n} \rfloor$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor \sqrt[3]{n} \rfloor$ ，代表循環執行? $\lfloor \sqrt[3]{n} \rfloor$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lfloor \sqrt[3]{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt[3]{n} \rfloor}=\lfloor \sqrt[3]{n} \rfloor$

省略系數和無關項后，數量級為? $\sqrt[3]{n}$ ，則時間復雜度為? $O(\sqrt[3]{n})=O(n^{\frac{1}{3}})$

（八）指數階

【例11.1】指數階? $O(2^{n})$ ?

int f(int n)
{if(n==1) return 1;else return f(n-1)+f(n-1);
}

計算時間復雜度

1.基本語句：

return 1;

return f(n-1)+f(n-1);

2.基本語句的語句頻度： $2^{n}-1$

3.時間復雜度： $T(n)=O(2^{n})$

遞歸函數無法按常規方式計算語句頻度

但是可以轉換思路，將遞歸過程模擬為二叉樹

一個遞歸函數當作二叉樹的一個節點

本例的函數比較特殊，f(n)剛好遞歸調用的是兩個f(n-1)

從二叉樹的視角來看，就是該節點連接下一層的兩個孩子

所以每個節點（不算葉子節點）都有兩個孩子，最終得到滿二叉樹

例如：f(4) 的遞歸滿二叉樹（如下圖）

每個節點（不算葉子節點）都有兩個孩子，最終得到滿二叉樹

當遞歸到葉子節點 f(1) 時，n==1，返回1，不向下遞歸

再看函數體，無論進 if 還是進 else，都只會執行1條語句

所以遞歸函數內基本語句的語句頻度是1

因為是滿二叉樹，且每個節點（即遞歸函數）的語句頻度是1

所以語句頻度之和 = 滿二叉樹的總節點數

如果了解滿二叉樹的性質，可以直接得出總節點數為? $2^{n}-1$

不了解也沒關系，下面逐步推導

我們知道二叉樹只有1個根節點

對于滿二叉樹，每個節點（不算葉子節點）都有兩個孩子

那么上層節點數與下層節點數是2倍關系，將 {節點數} 當作數列

第1層：根節點，節點數為? $a_{1}=1=2^{0}$

第2層：節點數為? $a_{2}=1\times 2=2=2^{1}$

第3層：節點數為? $a_{3}=2\times 2=4=2^{2}$

第4層：節點數為? $a_{4}=4\times 2=8=2^{3}$

第5層：節點數為? $a_{5}=8\times 2=16=2^{4}$

……

第n層：節點數為? $a_{n}=2^{n-1}$

可以看出其為等比數列

首項 $a_{1}=1$ ，公比? $q=2$ ?

等比數列通項公式? $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

求總節點數就是把第1層到第n層的所有節點數相加

其實相當于對 {節點數} 這個數列求和

代入等比數列求和公式

$S_{n}=\frac{a_{1}(1-q^{n})}{1-q}=\frac{1\cdot(1-2^{n})}{1-2}=-(1-2^{n})=2^{n}-1$ ?

（其中 n 既是問題規模，又是滿二叉樹的層數）

至此推導出語句頻度之和 = 滿二叉樹的總節點數? $=2^{n}-1$

省略系數和無關項后，數量級為? $2^{n}$ ，則時間復雜度為? $O(2^{n})$

【例11.2】指數階? $O(2^{n})$ ?

int f(int n)
{if(n==1 || n==2) return 1;else return f(n-2)+f(n-2);
}

計算時間復雜度

1.基本語句：

return 1;

return f(n-2)+f(n-2);

2.基本語句的語句頻度： $2^{\lfloor \frac{n+1}{2} \rfloor }-1$

3.時間復雜度： $T(n)=O(2^{n})$

遞歸函數無法按常規方式計算語句頻度

但是可以轉換思路，將遞歸過程模擬為二叉樹

一個遞歸函數當作二叉樹的一個節點

本例與【例11.1】有所不同

【例11.1】的遞歸過程是

$f(n)\rightarrow f(n-1)\rightarrow f(n-2)\rightarrow \cdots \rightarrow f(2) \rightarrow f(1)$

而本例f(n)遞歸調用的是兩個f(n-2)，缺少了f(n-1)這一層

所以這顆二叉樹是間隔一層向下遞歸的（仍是滿二叉樹，但層數不是n）

說一下奇偶數的性質

奇數 - 偶數 = 奇數，則?奇數n - 2 = 奇數

偶數 - 偶數 = 偶數，則偶數n - 2 = 偶數

由于間隔遞歸，且n不確定是奇數還是偶數

所以最終可能在奇數 f(1)返回，也可能在偶數 f(2)返回

下面分情況討論

當n為奇數時，最終在奇數 f(1)返回

f(n)遞歸過程如下

$f(n)\rightarrow f(n-2)\rightarrow f(n-4)\rightarrow \cdots \rightarrow f(3) \rightarrow f(1)$

從后往前看，當作數列

$1,3,\cdots,(n-4),(n-2),n$

則為等差數列

$a_{1}=1,\ a_{2}=3,\ \cdots,\ a_{m-2}=(n-4),\ a_{m-1}=(n-2),\ a_{m}=n$

首項? $a_{1}=1$ ，公差? $d=2$

等差數列通項公式? $a_{m}=a_{1}+(m-1)d=1+(m-1)\cdot2=2m-1$

代入最后一項?

$a_{m}=2m-1=n$

移項除以2求得m的值

$m=\frac{n+1}{2}$

數列從 $a_{1}$ ?到? $a_{m}$ 共m項，則遞歸過程有m層

所以奇數情況滿二叉樹的層數為? $m=\frac{n+1}{2}$

再看函數體，無論進 if 還是進 else，都只會執行1條語句

所以遞歸函數內基本語句的語句頻度是1

因為是滿二叉樹，且每個節點（即遞歸函數）的語句頻度是1

所以奇數情況語句頻度之和 = 滿二叉樹的總節點數 $=2^m-1=2^{\frac{n+1}{2}}-1$

當n為偶數時，最終在偶數 f(2)返回

f(n)遞歸過程如下

$f(n)\rightarrow f(n-2)\rightarrow f(n-4)\rightarrow \cdots \rightarrow f(4) \rightarrow f(2)$

從后往前看，當作數列

$2,4,\cdots,(n-4),(n-2),n$

則為等差數列

$a_{1}=2,\ a_{2}=4,\ \cdots,\ a_{m-2}=(n-4),\ a_{m-1}=(n-2),\ a_{m}=n$

首項? $a_{1}=2$ ，公差? $d=2$

等差數列通項公式? $a_{m}=a_{1}+(m-1)d=2+(m-1)\cdot2=2m$

代入最后一項?

$a_{m}=2m=n$

除以2求得m的值

$m=\frac{n}{2}$

數列從 $a_{1}$ ?到? $a_{m}$ 共m項，則遞歸過程有m層

所以偶數情況滿二叉樹的層數為? $m=\frac{n}{2}$

再看函數體，無論進 if 還是進 else，都只會執行1條語句

所以遞歸函數內基本語句的語句頻度是1

因為是滿二叉樹，且每個節點（即遞歸函數）的語句頻度是1

所以偶數情況語句頻度之和 = 滿二叉樹的總節點數 $=2^m-1=2^{\frac{n}{2}}-1$

類比【例5】的推導，可以使用? $\lfloor \ \rfloor$ 向下取整將兩式統一

先假設，總節點數公式可用向下取整統一為，奇數情況總節點數：? $2^{\lfloor \frac{n+1}{2} \rfloor }-1$

因為該式是從奇數情況推導出的，所以奇數肯定沒問題

代入驗證偶數情況，如果計算結果與偶數情況總節點數相同，說明可以統一

當n為偶數時，設? $n=2x$ （x是整數）

代入上式得

$2^{\lfloor \frac{n+1}{2} \rfloor }-1=2^{\lfloor \frac{2x+1}{2} \rfloor }-1$

進一步化簡得

$2^{\lfloor \frac{2x+1}{2} \rfloor }-1\\[1.5ex] =2^{\lfloor \frac{2x}{2}+\frac{1}{2} \rfloor }-1\\[1.5ex] =2^{\lfloor x+\frac{1}{2} \rfloor }-1\\[1.5ex] =2^{x}-1\\[1.5ex]$

因為向下取整時，只保留整數部分： $x$ ?，忽略小數部分：? $\frac{1}{2}$

前面設? $n=2x$ ，反之? $x=\frac{n}{2}$

將其代入得? $2^{x}-1=2^{\frac{n}{2}}-1$

將計算結果與偶數情況總節點數? $2^{\frac{n}{2}}-1$ ?進行對照

可以看到，兩式均為? $2^{\frac{n}{2}}-1$ ，則偶數情況也成立，所以可以統一為?? $2^{\lfloor \frac{n+1}{2} \rfloor }-1$

再假設，總節點數公式可用向下取整統一為，偶數情況總節點數：? $2^{\lfloor \frac{n}{2} \rfloor }-1$

因為該式是從偶數情況推導出的，所以偶數肯定沒問題

代入驗證奇數情況，如果計算結果與奇數情況總節點數相同，說明可以統一

當n為奇數時，設? $n=2x+1$ （x是整數）

代入上式得

$2^{\lfloor \frac{n}{2} \rfloor }-1=2^{\lfloor \frac{2x+1}{2} \rfloor }-1$

進一步化簡得

$2^{\lfloor \frac{2x+1}{2} \rfloor }-1\\[1.5ex] =2^{\lfloor \frac{2x}{2}+\frac{1}{2} \rfloor }-1\\[1.5ex] =2^{\lfloor x+\frac{1}{2} \rfloor }-1\\[1.5ex] =2^{x}-1\\[1.5ex]$

因為向下取整時，只保留整數部分： $x$ ?，忽略小數部分：? $\frac{1}{2}$

前面設? $n=2x+1$ ，反之? $x=\frac{n-1}{2}$

將其代入得? $2^{x}-1=2^{\frac{n-1}{2}}-1$

將計算結果與奇數情況總節點數? $2^{\frac{n+1}{2}}-1$ ?進行對照

可以看到，兩式一個為 $2^{\frac{n-1}{2}}-1$ ，另一個為 $2^{\frac{n+1}{2}}-1$ ，則奇數情況不成立，所以不能統一

所以最終統一為： $2^{\lfloor \frac{n+1}{2} \rfloor }-1$

語句頻度之和 = 滿二叉樹的總節點數? $=2^{\lfloor \frac{n+1}{2} \rfloor }-1$

省略系數和無關項后，數量級為? $2^{n}$ ，則時間復雜度為? $O(2^{n})$

因為? $2^{\lfloor \frac{n+1}{2} \rfloor } \approx 2^{\frac{n}{2}}$

而? $2^{\frac{n}{2}}$ ?可以寫成 $(\sqrt{2})^{n}$

所以有人認為時間復雜度應該是? $O((\sqrt{2})^{n})$ ?

? ?

根據大 $O$ 表示法在數學上的定義得

大 $O$ 表示法? $O (f(n))$ ?給出的是時間復雜度的一個漸近上界? $f(n)$

所以上述兩種均可漸近表示時間復雜度

不過為了方便統一理解，我還是傾向于? $O(2^{n})$

【例11.3】指數階? $O(2^{n})$ ?——斐波那契數列

int f(int n)
{if(n==1 || n==2) return 1;else return f(n-1)+f(n-2);
}

計算時間復雜度

1.基本語句：

return 1;

return f(n-1)+f(n-2);

2.基本語句的語句頻度： $\frac{2}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]-1$

3.時間復雜度： $T(n)=O(2^{n})$

由于左孩子 f(n-1)與右孩子 f(n-2)不在同一層

即左子樹連續遞歸，右子樹間隔遞歸

每個節點（即遞歸函數）的語句頻度是1

所以依然是語句頻度之和 = 二叉樹的總節點數

雖然總節點數不好定量計算，但是我們可以定性分析

【例11.1】 $f(n)=f(n-1)+f(n-1)$

【例11.2】 $f(n)=f(n-2)+f(n-2)$

【例11.3】 $f(n)=f(n-1)+f(n-2)$

可以分析出

$f(n-2)+f(n-2)\leqslant f(n-1)+f(n-2)\leqslant f(n-1)+f(n-1)$

所以得到時間復雜度關系

$\begin{matrix} O(\ f(n-2)+f(n-2)\ )\leqslant O(\ f(n-1)+f(n-2)\ )\leqslant O(\ f(n-1)+f(n-1)\ ) \end{matrix}$

前面已得出【例11.1】和【例11.2】的時間復雜度均為? $O(2^{n})$ ，即

$O(f(n-1)+f(n-1))=O(2^{n})$

$O(f(n-2)+f(n-2))=O(2^{n})$

則時間復雜度關系變為（類似于夾逼定理）

$O(2^{n})\leqslant O(\ f(n-1)+f(n-2)\ )\leqslant O(2^{n})$

所以定性分析，斐波那契數列的時間復雜度也是? $O(2^{n})$

斐波那契數列遞推公式： $f(n)=f(n-1)+f(n-2)$

通過特征方程推導可得通項公式： $F_{n}=\frac{1}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$

???

實際上，總節點數滿足遞推公式： $f(n)=f(n-1)+f(n-2)+1$ ? （即算上子樹的根節點）

通過特征方程推導可得通項公式： $2F_{n}-1=\frac{2}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]-1$

所以有人認為時間復雜度應該是? $O((\frac{1+\sqrt{5}}{2})^{n})$

根據大 $O$ 表示法在數學上的定義得

大 $O$ 表示法? $O (f(n))$ ?給出的是時間復雜度的一個漸近上界? $f(n)$

所以上述兩種均可漸近表示時間復雜度

不過為了方便統一理解，我還是傾向于? $O(2^{n})$

六、考研408真題

【2011年第 1 題】設 n 是描述問題規模的非負整數，下列程序段的時間復雜度是（A）

x=2; 
while(x<n/2) x=2*x;

A． $O(log_{2}n)$ ? ? B． $O(n)$ ? ? C． $O(nlog_{2}n)$ ? ? D． $O(n^{2})$

本題與【例8.2】對數階相似，只不過循環條件不同?

計算時間復雜度

1.基本語句：x=2*x;

2.基本語句的語句頻度： $\sum\limits_{k=1}^{\lceil log_{2}(n) \rceil-2} 1=\overbrace{1+\cdots +1}^{\lceil log_{2}(n) \rceil-2}=\lceil log_{2}(n) \rceil-2$

3.時間復雜度： $T(n)=O(log_{2}{n})$

while循環可以理解為

循環變量初始化
while( 循環條件 )
{循環體【其中包含循環變量自增】
}

本例比較特殊，因為循環體只有1條語句

所以?x=2*x，既是循環體，也是循環變量自增

所以循環變量 x?不能反映實際的循環執行次數

設循環的執行次數為 k 次

為探尋循環變量 x?的變化規律，將其當作數列

循環變量初始化：x=2，則首項? $a_{1}=2$

循環變量自增：x*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=2\times 2^{n-1}=2^{n}$

則循環變量 x?隨著通項公式改變?

$x=a_{1}=2^{1} \\[1.5ex] x=a_{2}=2^{2} \\[1.5ex] x=a_{3}=2^{3} \\[1.5ex] \cdots \\[1.5ex] x=a_{k}=2^{k}$

所以最后一次循環（第k次循環）時

$x=2^{k}$

又因為循環條件是 $x<\frac{n}{2}$

不等式兩邊都不是整數表達式，不好計算最后一次循環的x值

所以不追求列等式，而是直接將? $x=2^{k}$ 代入不等式，得

$x=2^{k}< \frac{n}{2}$

不等式兩邊同時乘2

$2^{k+1}<n$

不等式兩邊同時取對數

$k+1<log_{2}(n)$

移項，得到循環執行次數k的范圍

$k<log_{2}(n)-1$

根據【例8.2】中的結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

代入本題：

k是整數，不等式關系為? $k<log_{2}(n)-1$ ?，則整數k的最大值? $k_{max}=\lceil log_{2}(n)-1 \rceil-1=\lceil log_{2}(n) \rceil-2$

現在就可以列求和式計算了

while循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 k?從1到? $\lceil log_{2}(n) \rceil-2$ ，代表循環執行? $\lceil log_{2}(n) \rceil-2$ 次

則語句頻度為：

$\sum\limits_{k=1}^{\lceil log_{2}(n) \rceil-2} 1=\overbrace{1+\cdots +1}^{\lceil log_{2}(n) \rceil-2}=\lceil log_{2}(n) \rceil-2$

省略系數和無關項后，數量級為? $log_{2}{n}$ ，則時間復雜度為? $O(log_{2}{n})$

【2012年第 1 題】求整數? $n\ (n\geqslant0)$ ?階乘的算法如下，其時間復雜度是（B）

int fact(int n)
{if(n<=1) return 1;else return n*fact(n-1);
}

A． $O(log_{2}n)$ ? ? B． $O(n)$ ? ? C． $O(nlog_{2}n)$ ? ? D． $O(n^{2})$

計算時間復雜度

1.基本語句：

return 1;

return n*fact(n-1);

2.基本語句的語句頻度： $n$

3.時間復雜度： $T(n)=O(n)$

遞歸函數無法按常規方式計算語句頻度

但是可以轉換思路，將遞歸過程模擬為二叉樹

一個遞歸函數當作二叉樹的一個節點

函數f(n)遞歸調用的是f(n-1)

從二叉樹的視角來看，就是該節點連接下一層的一個孩子

所以每個節點（不算葉子節點）都只有一個孩子，最終得到"單叉"的二叉樹

其實這棵"單叉"的二叉樹就是線性表（或稱二叉樹退化為線性表）

縱向可能看不出來是線性表，改成橫向就一目了然

例如：f(4)的遞歸二叉樹（退化為線性表）如下圖

??

再看函數體，無論進 if 還是進 else，都只會執行1條語句

所以遞歸函數內基本語句的語句頻度是1

又因為退化為線性表，所以總節點數就是n

所以?語句頻度之和 = 線性表總節點數? $=n$

省略系數和無關項后，數量級為? $n$ ，則時間復雜度為? $O(n)$

【2013年第 1 題】已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是（D）

A． $O(n)$ ? ? B． $O(mn)$ ? ? C． $O(min(m,n))$ ? ? D． $O(max(m,n))$

升序改降序：只需在遍歷時，用頭插法將元素插入新鏈表

比如原鏈表為1、2、3、4、5，遍歷時用頭插法插入新鏈表，新鏈表變為5、4、3、2、1

這樣做的好處是，遍歷還是正常順序，不需要倒著來

??

鏈表合并的最壞情況：兩鏈表交替遍歷

舉例：鏈表1是：1、3、5、7、9，鏈表2是：2、4、6

那么遍歷合并為新鏈表時，二者就會交替遍歷：1、2、3、4、5、6

然后新鏈表將鏈表1的剩余部分：7、9 并入

鏈表1的長度m=5，鏈表2的長度n=3

那么整個合并過程會將? $m+n=5+3=8$ ?個數并入新鏈表

如果m，n沒有給出具體值，那么并入過程是 $m+n$ ?個數并入

數量級為 $m+n$ ，所以時間復雜度為? $O(m+n)$

如果兩個鏈表長度中的最大值用? $max(m,n)$ ?表示，則

$m\leqslant max(m,n)$

$n\leqslant max(m,n)$

相加得

$m+n\leqslant 2\cdot max(m,n)$

所以最多有? $2\cdot max(m,n)$ ?個數合并，省略系數后，數量級為 $max(m,n)$ ，則

$O(m+n)\leqslant O(max(m,n))$

所以時間復雜度也可以看作是? $O(max(m,n))$

前面是舉例分析得出的，也可以拿代碼來分析

原題沒有代碼，這里給出一段鏈表合并的代碼（以不帶頭節點的鏈表為例）

《頭插法實現兩升序鏈表合并為降序鏈表》

//頭插法實現兩升序鏈表合并為降序鏈表
ListNode* merge(ListNode* L1, ListNode* L2)
{ListNode *head = NULL; // 新鏈表的頭指針ListNode *temp; //臨時指針while (L1 != NULL && L2 != NULL){// 比較兩個鏈表當前節點的值if (L1->val <= L2->val){//取出L1節點temp = L1;L1 = L1->next;// 頭插法：將L1節點插入新鏈表頭部temp->next = head;head = temp;}else{//取出L2節點temp = L2;L2 = L2->next;// 頭插法：將L2節點插入新鏈表頭部temp->next = head;head = temp;}}// 處理剩余節點（L1更長）while (L1 != NULL){//取出L1節點temp = L1;L1 = L1->next;// 頭插法：將L1節點插入新鏈表頭部temp->next = head;head = temp;}// 處理剩余節點（L2更長）while (L2 != NULL){//取出L2節點temp = L2;L2 = L2->next;// 頭插法：將L2節點插入新鏈表頭部temp->next = head;head = temp;}return head;
}

計算時間復雜度

1.基本語句：

temp?=?L1;? ?//或temp?=?L2;

L1?=?L1->next;? ?//或L2?=?L2->next;

temp->next?=?head;

head?=?temp;

2.基本語句的語句頻度： $4\times(2n)+4\times(m-n)=4\times(2n+m-n)=4(m+n)$

3.時間復雜度： $T(n)=O(m+n)\leqslant O(max(m,n))$

假設兩鏈表長度m>n（反之同理）

則鏈表1的前n項與鏈表2的n項，交替并入新鏈表（第一個while循環）

鏈表1剩余的m-n項，直接并入新鏈表（后面兩個while循環二選一）

由于并入操作都是4條語句，所以不用區分是鏈表1還是鏈表2

交替并入時的語句頻度? $=4\times n+4\times n=4\times(2n)$

剩余并入時的語句頻度? $=4\times(m-n)$

所以語句頻度之和? $=4\times(2n)+4\times(m-n)=4\times(2n+m-n)=4(m+n)$

省略系數后，數量級為? $m+n$ ，所以時間復雜度為? $O(m+n)$

如果兩個鏈表長度的最大值用? $max(m,n)$ ?表示，則

$m\leqslant max(m,n)$

$n\leqslant max(m,n)$

相加得

$m+n\leqslant 2\cdot max(m,n)$

所以最多有? $2\cdot max(m,n)$ ?個數合并，省略系數后，數量級為 $max(m,n)$ ，則

$O(m+n)\leqslant O(max(m,n))$

所以時間復雜度也可以看作是? $O(max(m,n))$

有人可能會疑惑，為什么剩余部分并入還要耗費時間，用指針直接連上剩余部分不就行了？

這就是不審題的結果，題目要求是：兩升序鏈表合并為降序鏈表

如果直接將剩余部分連上，豈不是把一段升序鏈表并入降序鏈表，那結果就不對了

剩余部分并入之所以耗費時間，是因為要用頭插法將這部分升序鏈表變為降序鏈表

（下面僅作探究，與本題無關）

引申一下，假如題目要求改為：兩升序鏈表合并為升序鏈表

這就跟上面提出的思路一樣了，兩鏈表交替并入，最后連接剩余部分

《尾插法實現兩升序鏈表合并為升序鏈表》

//尾插法實現兩升序鏈表合并為升序鏈表
ListNode* merge(ListNode* L1, ListNode* L2)
{ListNode *head = NULL; // 新鏈表的頭指針ListNode *tail = NULL; // 新鏈表的尾指針//確定第一個節點if (L1->val <= L2->val){head = L1;L1=L1->next;}else{head = L2;L2=L2->next;}tail = head;// 尾指針指向第一個節點while (L1 != NULL && L2 != NULL){// 比較兩個鏈表當前節點的值if (L1->val <= L2->val){// 將L1節點接入鏈表尾部tail->next = L1;L1 = L1->next;}else{// 將L2節點接入鏈表尾部tail->next = L2;L2 = L2->next;}}// 連接剩余鏈表if (L1 != NULL){tail->next = L1;}else{tail->next = L2;}return head;
}

計算時間復雜度

1.基本語句：

tail->next?=?L1;? ?//或tail->next?=?L2;

L1?=?L1->next;? ?//或L2?=?L2->next;

2.基本語句的語句頻度： $2+4n+1=4n+3$

3.時間復雜度： $T(n)=O(n)=O(min(m,n))$

假設兩鏈表長度m>n（反之同理）

因為不帶頭節點，所以需要確定第一個節點，將鏈表1的第一個節點并入新鏈表（if...else）

鏈表1的n項與鏈表2的n項，交替并入新鏈表（while循環）

用指針直接連接鏈表1的剩余部分（if...else）

由于并入操作都是2條語句，所以不用區分是鏈表1還是鏈表2

第一個節點并入時的語句頻度? $=2\times 1=2$

交替并入時的語句頻度? $=2\times n+2\times n=4n$

指針連接剩余部分時的語句頻度? $=1$

所以語句頻度之和? $=2+4n+1=4n+3$

省略系數和無關項后，數量級為? $n$ ，所以時間復雜度為? $O(n)$

? ??

因為前面假設兩鏈表長度m>n

如果兩個鏈表長度的最小值用? $min(m,n)$ ?表示，則

$n= min(m,n)$

所以時間復雜度也可以看作是? $O(n)=O(min(m,n))$

假設兩鏈表長度m>n，可以得出以下結論:

合并后順序相反（升+升→降?或降+降→升），則時間復雜度為? $O(m+n)\leqslant O(max(m,n))$

合并后順序相同（升+升→升或降+降→降），則時間復雜度為? $O(n)=O(min(m,n))$

? ??

? ? ?

【2014年第 1 題】下列程序段的時間復雜度是（C）

count=0; 
for(k=1; k<=n; k*=2) for(j=1; j<=n; j++) count++;

A． $O(log_{2}n)$ ? ? B． $O(n)$ ? ? C． $O(nlog_{2}n)$ ? ? D． $O(n^{2})$

本題與【例9】線性對數階如出一轍，只不過內外循環互換了

計算時間復雜度

1.基本語句：count++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1 \times \sum\limits_{j=1}^{n}1= \lfloor log_{2}{(n)}+1\rfloor \times n=n\times \lfloor log_{2}{(n)}+1\rfloor$

3.時間復雜度： $T(n)=O(nlog_{2}{n})$

嵌套無關循環，所以內外層循環互不干擾，語句頻度獨立計算

因為內層循環條件是 j<=n?，所以 j?能取的最大值（即求和上限）是：n

內層循環只有1條基本語句，所以求和表達式（通項公式）是1

所以內層循環的語句頻度為

$\sum\limits_{j=1}^{n}1 =\overbrace{1+\cdots +1}^{n} = n$

因為外層循環變量自增不是以往的 k++，而是 k*=2

所以循環變量 k?不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 k?的變化規律，將其當作數列

循環變量初始化：k=1，則首項? $a_{1}=1$

循環變量自增：k*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 k?隨著通項公式改變?

$k=a_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] k=a_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] k=a_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] k=a_{x}=2^{x-1} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$k=2^{x-1}$

又因為循環條件是 $k \leqslant n$

所以最后一次循環時 $k=n$ ，則

$k=2^{x-1}= n$

等式兩邊同時取對數

$x-1=log_{2}{(n)}$

移項，得到循環執行次數x的值

$x=log_{2}{(n)}+1$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor log_{2}{(n)}+1\rfloor$

? ??

現在就可以列求和式計算了

內層循環可以看作是外層循環體的1條基本語句，則求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor log_{2}{(n)}+1\rfloor$ ，代表循環執行? $\lfloor log_{2}{(n)}+1\rfloor$ 次

所以外層循環的語句頻度為：

$\sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor log_{2}{(n)}+1\rfloor}=\lfloor log_{2}{(n)}+1\rfloor$

根據統計學乘法原理，兩式相乘得語句頻度

$\sum\limits_{x=1}^{\lfloor log_{2}{(n)}+1\rfloor} 1 \times \sum\limits_{j=1}^{n}1= \lfloor log_{2}{(n)}+1\rfloor \times n=n\times \lfloor log_{2}{(n)}+1\rfloor$

省略系數和無關項后，數量級為? $nlog_{2}{n}$ ，則時間復雜度為? $O(nlog_{2}{n})$

【2017年第 1 題】下列函數的時間復雜度是（B）

int func(int n)
{ int i=0,sum=0; while(sum<n) sum+=++i; return i;
}

A． $O(log_{2}n)$ ? ? B． $O(n^{\frac{1}{2}})$ ? ? C． $O(n)$ ? ? D． $O(nlog_{2}n)$

計算時間復雜度

1.基本語句：sum+=++i;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1} 1=\overbrace{1+\cdots +1}^{\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1}=\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1$

3.時間復雜度： $T(n)=O(\sqrt{n})=O(n^{\frac{1}{2}})$

因為本例的循環條件不是以往的 i<n，而是 sum<n

所以循環變量 i?不能反映實際的循環執行次數

設循環的執行次數為 x 次

while循環體【包含循環變量自增】只有1條基本語句：sum+=++i;

前置自增表達式 ++i 有兩個效果：

一是讓 i 自增為 i+1，二是把 i+1 作為整個自增表達式的值

所以 sum+=++i; 相當于分兩步：

先執行++i; 讓 i?自增為 i+1，后執行sum+=(i+1); 進行求和

所以sum始終是對 i+1 進行求和

為探尋?i+1 的變化規律，將其當作數列

循環變量初始化：i=0，則 i+1=1，首項? $a_{1}=1$

循環變量自增：++i，公差? $d=1$ ，即等差數列

等差數列 {i+1} 的通項公式： $a_{n}=a_{1}+(n-1)d=1+(n-1)=n$

則等差數列 {i+1} 隨著通項公式改變?

$i+1=a_{1}=0+1=1 \\[1.5ex] i+1=a_{2}=1+1=2 \\[1.5ex] i+1=a_{3}=2+1=3 \\[1.5ex] \cdots \\[1.5ex] i+1=a_{x}=(x-1)+1=x$

因為sum始終是對 i+1 進行求和

所以可以將其看作是等差數列 {i+1} 的前n項和

代入前n項和公式： $S_{n}=\frac{n(a_{1}+a_{n})}{2}=\frac{n(1+n)}{2}=\frac{n(n+1)}{2}$

注意，本題是while循環，初次循環判斷的是sum的初值0，而初值與 i+1 無關，所以單設一個 $S_{0}$

后續sum對 i+1 求和，則sum隨著前n項和公式改變（循環共執行x次，首項是? $S_{0}$ ，則末項是? $S_{x-1}$ ）

$sum=S_{0}=0 \\[1.5ex] sum=S_{1}=\frac{1(1+1)}{2}=1 \\[1.5ex] sum=S_{2}=\frac{2(2+1)}{2}=3 \\[1.5ex] sum=S_{3}=\frac{3(3+1)}{2}=6 \\[1.5ex] \cdots \\[1.5ex] sum=S_{x-1}=\frac{(x-1)(x-1+1)}{2}=\frac{x(x-1)}{2}$

所以最后一次循環（第x次循環）時

$sum=\frac{x(x-1)}{2}$

又因為循環條件是 $sum <n$

不等式兩邊不都是整數表達式，不好計算最后一次循環的x值

所以不追求列等式，而是直接將? $sum=\frac{x(x-1)}{2}$ 代入不等式，得

$sum=\frac{x(x-1)}{2}< n$

不等式兩邊同時乘2

$x(x-1)<2n$

不等式左邊展開得

$x^{2}-x<2n$

移項，得一元二次不等式

$x^{2}-x-2n<0$

則各項系數? $a=1,b=-1,c=-2n$ ?（其中n是問題規模， $n\geqslant 0$ ）

?

根據一元二次函數圖像、方程、不等式的對應關系

因為 $a=1>0$ ，所以函數圖像開口向上

因為 $\Delta =b^{2}-4ac=(-1)^{2}-4\cdot1\cdot (-2n)=8n+1>0$ ，所以方程有兩實數根

因為 $x^{2}+x-2n<0$ ，所以不等式的解集位于兩根之間

將? $a=1,b=-1,c=-2n$ 代入求根公式，得出兩根

$x_{1}=\frac{-b-\sqrt{b^{2}-4ac}}{2a}=\frac{-(-1)-\sqrt{1^{2}-4\cdot 1 \cdot(-2n)}}{2\cdot 1}=\frac{1-\sqrt{1+8n}}{2}=-\frac{\sqrt{8n+1}}{2}+\frac{1}{2}$

$x_{2}=\frac{-b+\sqrt{b^{2}-4ac}}{2a}=\frac{-(-1)+\sqrt{1^{2}-4\cdot 1 \cdot(-2n)}}{2\cdot 1}=\frac{1+\sqrt{1+8n}}{2}=\frac{\sqrt{8n+1}}{2}+\frac{1}{2}$

所以x的取值范圍為? $(-\frac{\sqrt{8n+1}}{2}+\frac{1}{2})<x<(\frac{\sqrt{8n+1}}{2}+\frac{1}{2})$

根據【例8.2】中的結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

代入本題：

x是整數，不等式關系為? $x<(\frac{\sqrt{8n+1}}{2}+\frac{1}{2})$ ?，則整數x的最大值? $x_{max}=\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1$

現在就可以列求和式計算了

while循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1$ ，代表循環執行? $\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1} 1=\overbrace{1+\cdots +1}^{\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1}=\lceil \frac{\sqrt{8n+1}}{2}+\frac{1}{2} \rceil-1$

省略系數和無關項后，數量級為? $\sqrt{n}$ ，則時間復雜度為? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

其實做選擇題沒必要這么精確

上面已列出關于循環條件的不等式

$sum=\frac{x(x-1)}{2}< n$

把x-1近似為x，并將整個式子看作等式

$sum=\frac{x^{2}}{2}= n$

得出循環執行次數的近似值

$x\approx \sqrt{2n}$

則語句頻度近似值為

$\sum\limits_{x=1}^{\sqrt{2n}} 1 \approx \overbrace{1+\cdots +1}^{\sqrt{2n}}\approx \sqrt{2n}$

則時間復雜度為

$O(\sqrt{n})=O(n^{\frac{1}{2}})$

???

?????

【2019年第 1 題】設 n 是描述問題規模的非負整數，下列程序段的時間復雜度是（B）

x=0; 
while(n>=(x+1)*(x+1)) x=x+1;

A． $O(log_{2}n)$ ? ? B． $O(n^{\frac{1}{2}})$ ? ? C． $O(n)$ ? ? D． $O(n^{2})$

本題與【例10.1】根號階相似，只不過循環變量初始化和循環條件不同

計算時間復雜度

1.基本語句：x=x+1;

2.基本語句的語句頻度： $\sum\limits_{k=1}^{\lfloor \sqrt{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{n} \rfloor}=\lfloor \sqrt{n} \rfloor$

3.時間復雜度： $T(n)=O(\sqrt{n})=O(n^{\frac{1}{2}})$

?

因為本例的循環條件不是以往的 x<=n，而是 n>=(x+1)*(x+1)

但循環條件通常把循環變量表達式寫在前面，如果反過來寫，就是(x+1)*(x+1)<=n

所以循環變量 x?不能反映實際的循環執行次數

設循環的執行次數為 k 次

為探尋循環條件?(x+1)*(x+1) 的變化規律，將其當作數列

循環變量初始化：x=0

循環變量自增：x=x+1

將循環變量 x?的值依次代入循環條件 (x+1)*(x+1)，探尋數列規律

$(x+1)*(x+1)=a_{1}=(0+1)\times (0+1)=1\times 1=1^{2} \\[1.5ex] (x+1)*(x+1)=a_{2}=(1+1)\times (1+1)=2\times 2=2^{2} \\[1.5ex] (x+1)*(x+1)=a_{3}=(2+1)\times (2+1)=3\times 3=3^{2} \\[1.5ex] \cdots \\[1.5ex] (x+1)*(x+1)=a_{k}=((k-1)+1)\times ((k-1)+1)=k \times k=k^{2} \\[1.5ex]$

所以最后一次循環（第k次循環）時

$(x+1)*(x+1)=k^{2}$

又因為循環條件是 $(x+1)*(x+1)\leqslant n$

所以最后一次循環時 $(x+1)*(x+1)=n$ ，則

$(x+1)*(x+1)=k^{2}=n$

等式兩邊同時開平方，得到循環執行次數k的值

$k=\sqrt{n}$

但是循環執行次數只能是整數，所以k還要向下取整

$k=\lfloor \sqrt{n} \rfloor$

現在就可以列求和式計算了

while循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 k?從1到? $\lfloor \sqrt{n} \rfloor$ ，代表循環執行? $\lfloor \sqrt{n} \rfloor$ 次

則語句頻度為：

$\sum\limits_{k=1}^{\lfloor \sqrt{n} \rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{n} \rfloor}=\lfloor \sqrt{n} \rfloor$

省略系數和無關項后，數量級為? $\sqrt{n}$ ，則時間復雜度為? $O(\sqrt{n})=O(n^{\frac{1}{2}})$

【2022年第 1 題】下列程序段的時間復雜度是（B）

int sum=0;
for(int i=1; i<n; i*=2)for(int j=0; j<i; j++)sum++;

A． $O(log_{2}n)$ ? ? B． $O(n)$ ? ? C． $O(nlog_{2}n)$ ? ? D． $O(n^{2})$

本題看著與【2014年第 1 題】類似，但實際上不同

2014年是嵌套無關循環，而本題是?嵌套相關循環

計算時間復雜度

1.基本語句：sum++;

2.基本語句的語句頻度：

$\begin{matrix} \sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} \sum\limits_{j=0}^{i-1}1=\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} \sum\limits_{j=1}^{i}1 =\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} i =\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} 2^{x-1} =S_{\lceil log_{2}{(n)} \rceil} =\frac{2^{0}(1-2^{\lceil log_{2}{(n)} \rceil})}{1-2} =2^{\lceil log_{2}{(n)} \rceil}-1 \approx 2^{ log_{2}{(n)}}-1 \approx n-1 \end{matrix}$

3.時間復雜度： $T(n)=O(n)$

因為是嵌套相關循環，內外層循環相關，不能分開計算

但是可以先列出來求和式的上下限，再多重求和

因為內層循環條件是 j<i?，所以 j?能取的最大值（即求和上限）是：i-1

所以內層循環的求和式上下限列為

$\sum\limits_{j=0}^{i-1}$

因為外層循環變量自增不是以往的 i++，而是 i*=2

所以循環變量 i?不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 i?的變化規律，將其當作數列

循環變量初始化：i=1，則首項? $a_{1}=1$

循環變量自增：i*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 i?隨著通項公式改變?

$i=a_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] i=a_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] i=a_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] i=a_{x}=2^{x-1} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i=2^{x-1}$

又因為循環條件是 $i<n$

不等式兩邊不都是整數表達式，不好計算最后一次循環的x值

所以不追求列等式，而是直接將? $i=2^{x-1}$ 代入不等式，得

$i=2^{x-1}< n$

不等式兩邊同時取對數

$x-1<log_{2}{(n)}$

移項，得到循環執行次數x的范圍

$x<log_{2}{(n)}+1$

根據【例8.2】中的結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

代入本題：

x是整數，不等式關系為? $x<log_{2}{(n)}+1$ ?，則整數x的最大值? $x_{max}=\lceil log_{2}{(n)}+1 \rceil -1=\lceil log_{2}{(n)} \rceil$

令求和變量 x?從1到? $\lceil log_{2}{(n)} \rceil$ ，代表循環執行? $\lceil log_{2}{(n)} \rceil$ 次

所以外層循環的求和式上下限為：

$\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil}$

??

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} \sum\limits_{j=0}^{i-1}1$

雙重求和可以加括號以區分

$\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} \sum\limits_{j=0}^{i-1}1=\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} (\sum\limits_{j=0}^{i-1}1)$

可以類比復合函數，先計算括號內的

$\sum\limits_{j=0}^{i-1}1 =\sum\limits_{j=0+1}^{i-1+1}1=\sum\limits_{j=1}^{i}1=\overbrace{1+\cdots +1}^{i} = i$

將括號內的求和式替換為計算結果，雙重求和變為

$\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} (\sum\limits_{j=0}^{i-1}1)=\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} i$

注意，此時求和變量 x 與求和表達式 i 是不同符號，直接展開無意義

所以需要把?i 替換為關于求和變量 x 的表達式

前面已推導出最后一次循環（第x次循環）時

$i=2^{x-1}$

把 $i$ ?替換

$\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} i=\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} 2^{x-1}$

將其展開得

$\begin{matrix} \sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} 2^{x-1}=2^{1-1}+2^{2-1}+\cdots+2^{\lceil log_{2}{(n)} \rceil-1}=2^{0}+2^{1}+\cdots+2^{\lceil log_{2}{(n)} \rceil-1} \end{matrix}$

此時變為等比數列求和

首項? $a_{1}=2^{0}$ ，公比? $q=2$

代入等比數列求和公式?

$S_{n}=\frac{a_{1}(1-q^{n})}{1-q}$ ?

得到語句頻度

$\sum\limits_{x=1}^{\lceil log_{2}{(n)} \rceil} 2^{x-1}\\[1.5ex] =S_{\lceil log_{2}{(n)} \rceil}\\[1.5ex] =\frac{2^{0}(1-2^{\lceil log_{2}{(n)} \rceil})}{1-2}\\[1.5ex] =2^{\lceil log_{2}{(n)} \rceil}-1\\[1.5ex] \approx 2^{ log_{2}{(n)}}-1\\[1.5ex] \approx n-1$

解釋一下，根據對數的定義可知

$2^{log_{2}{(n)}}=n$

因為? $\lceil log_{2}{(n)} \rceil$ 與 $log_{2}{(n)}$ 差距很小，所以

$2^{\lceil log_{2}{(n)} \rceil} \approx 2^{log_{2}{(n)}} \approx n$ ?

同時減1得

$2^{\lceil log_{2}{(n)} \rceil}-1 \approx 2^{log_{2}{(n)}} -1\approx n-1$

省略系數和無關項后，數量級為? $n$ ，則時間復雜度為? $O(n)$

【2023年第 1 題】下列對順序存儲的有序表（長度為n）實現給定操作的算法中，平均時間復雜度為 $O(1)$ 的是（D）

A．查找包含指定值元素的算法

B．插入包含指定值元素的算法

C．刪除第? $i\ (1\leqslant i \leqslant n)$ ?個元素的算法

D．獲取第? $i\ (1\leqslant i \leqslant n)$ ?個元素的算法

題目給定的是順序存儲，則有序表使用數組實現

typedef struct
{int data[MAXSIZE];  // 存儲元素的數組int n;  // 當前表長
} SeqList;

??

有序表一般采用折半查找（二分查找）算法

A．查找

// A. 查找指定值元素——折半查找（二分查找）
int search(SeqList *list, int value)
{int low = 0, high = list->n-1,mid;while (low <= high){mid = (low + high)/2;if (list->data[mid] == value)return mid;  // 找到返回下標else if (list->data[mid] < value)low = mid+1;elsehigh = mid-1;}return -1;  // 未找到
}

計算時間復雜度

1.基本語句：

mid = (low + high) / 2;?

return mid;

low = mid + 1;

high = mid - 1;

2.基本語句的語句頻度： $2\times[\frac{n+1}{n}log_{2}(n+1)-1] \approx 2\times[\frac{n}{n}log_{2}(n+1)-1] \approx 2\times[log_{2}(n+1)-1]$

3.時間復雜度： $T(n)=O(log_{2}{n})$

本函數有兩種結束方式：

一是查找失敗，最終low>high，while循環結束，函數返回 -1

二是查找成功，list->data[mid] == value，函數返回 mid

再看基本語句

while循環體中，mid = (low + high) / 2; 這1條語句是必做的

其他三條語句通過if……else if……else判斷后，三選一

所以每輪循環體執行1+1=2條基本語句

語句頻度=基本語句條數?x 循環執行次數

已經得出基本語句條數為2條，如果再知道循環執行次數就能算出語句頻度

下面只探究查找成功情況下的循環執行次數

這里需要引入平均查找長度?的概念

從定義來看，平均查找長度其實就是平均比較次數

而每次比較，對應到代碼，就是循環體中的if……else if……else判斷

所以每執行一次循環體，就是一次比較

則循環執行次數=平均比較次數=平均查找長度

? ??

所以求循環執行次數轉為求平均查找長度

推導過程比較復雜，這里直接給出結果，折半查找的平均查找長度=? $\frac{n+1}{n}log_{2}(n+1)-1$

如果想了解推導過程可以看我的這篇文章——《?折半查找的平均查找長度公式推導?》

所以循環執行次數=折半查找的平均查找長度=? $\frac{n+1}{n}log_{2}(n+1)-1$

語句頻度=基本語句條數?x 循環執行次數=基本語句條數?x 平均查找長度

$=2\times[\frac{n+1}{n}log_{2}(n+1)-1] \approx 2\times[\frac{n}{n}log_{2}(n+1)-1] \approx 2\times[log_{2}(n+1)-1]$

（注：因為對數有小括號，所以整個平均查找長度用中括號括住，并不是向上取整或向下取整）

解釋一下，因為n+1與n差距很小，所以

$\frac{n+1}{n}\approx \frac{n}{n} \approx 1$

代入得

$2\times[\frac{n+1}{n}log_{2}(n+1)-1] \approx 2\times[\frac{n}{n}log_{2}(n+1)-1] \approx 2\times[log_{2}(n+1)-1]$

省略系數和無關項后，數量級為? $log_{2}n$ ，則時間復雜度為? $O(log_{2}n)$

所以查找過程的時間復雜度是 $O(log_{2}n)$ ，不是 $O(1)$

B．插入

// B. 插入指定值元素（保持有序）
int insert(SeqList *list, int value)
{if (list->n >= MAXSIZE){printf("表已滿，無法插入\n");return 0;}int i = list->n-1;// 從后向前找到插入位置while (i >= 0 && list->data[i] > value){list->data[i+1] = list->data[i];  // 元素后移i--;}list->data[i+1] = value;  // 插入新元素list->n++;  // 表長增加return 1;  // 成功插入
}

計算時間復雜度

1.基本語句：

list->data[i + 1] = list->data[i];

i--;

2.基本語句的語句頻度： $2\times (n-1-\lfloor \frac{n-1}{2} \rfloor)\approx 2\times(n-1-\frac{n-1}{2}) \approx 2\times \frac{n-1}{2} \approx n-1$

3.時間復雜度： $T(n)=O(n)$

因為是在數組中插入，需要給待插入元素留空位

所以從后往前遍歷，將比它大的每個元素都向后移動一格

最后將待插入元素插到空位中，并改變表長

舉例：插入值為5的元素

以待插入數據在中間為例

表長為n，表尾下標為n-1，則中間位置為 $\lfloor \frac{n-1}{2} \rfloor$

則向后移動的元素有? $n-1-\lfloor \frac{n-1}{2} \rfloor$

基本語句是循環體中的2條語句

所以語句頻度為? $2\times (n-1-\lfloor \frac{n-1}{2} \rfloor)\approx 2\times(n-1-\frac{n-1}{2}) \approx 2\times \frac{n-1}{2} \approx n-1$

省略系數和無關項后，數量級為? $n$ ，則時間復雜度為? $O(n)$

所以插入過程的時間復雜度是? $O(n)$ ，不是 $O(1)$

? ?

C．刪除

// C. 刪除第i個元素（0≤i≤n-1）
int delete (SeqList *list, int i)
{if (i < 0 || i > list->n-1){printf("位置非法\n");return 0;}// 將第i+1個位置及以后的元素前移for (int j = i+1; j < list->n; j++){list->data[j-1] = list->data[j];}list->n--;  // 表長減1return 1;        // 成功刪除
}

計算時間復雜度

1.基本語句：list->data[j - 1] = list->data[j];

2.基本語句的語句頻度： $n-1-\lfloor \frac{n-1}{2} \rfloor \approx n-1-\frac{n-1}{2} \approx \frac{n-1}{2}$

3.時間復雜度： $T(n)=O(n)$

刪除與插入如出一轍，只不過一個向前移動，一個向后移動

因為是在數組中刪除，只需要將待刪除元素的位置覆蓋掉

所以從前往后遍歷，將比它大的每個元素都向前移動一格，并改變表長

舉例：刪除a[4]位置的元素

? ?

以待刪除數據在中間為例

表長為n，表尾下標為n-1，則中間位置為 $\lfloor \frac{n-1}{2} \rfloor$

則向前移動的元素有? $n-1-\lfloor \frac{n-1}{2} \rfloor$

基本語句是循環體中的1條語句

因為此處為for循環，循環變量自增不在循環體中，所以基本語句只有1條

所以語句頻度為? $n-1-\lfloor \frac{n-1}{2} \rfloor \approx n-1-\frac{n-1}{2} \approx \frac{n-1}{2}$

省略系數和無關項后，數量級為? $n$ ，則時間復雜度為? $O(n)$

所以刪除過程的時間復雜度是? $O(n)$ ，不是 $O(1)$

D．獲取

// D. 獲取第i個元素（0≤i≤n-1）
int get(SeqList *list, int i)
{if (i < 0 || i > list->n-1){printf("位置非法\n");return -1;  // 返回-1表示錯誤（假設元素均為非負整數）}return list->data[i];  // 返回元素值
}

計算時間復雜度

1.基本語句：return list->data[i - 1];

2.基本語句的語句頻度： $1$

3.時間復雜度： $T(n)=O(1)$

獲取元素僅需1條return語句，所以語句頻度為? $1$

省略系數和無關項后，數量級為? $1$ ，則時間復雜度為? $O(1)$

所以獲取過程的時間復雜度就是? $O(1)$

? ??

【2025年第 1 題】下列程序段的時間復雜度是（B）

int count=0;
for(int i=0; i*i<n; i++)for(int j=0; j<i; j++)count++;

A． $O(log_{2}n)$ ? ? B． $O(n)$ ? ? C． $O(nlog_{2}n)$ ? ? D． $O(n^{2})$

本例類似于將【例3】嵌套相關循環和【例10.2】根號階結合起來

計算時間復雜度

1.基本語句：count++;

2.基本語句的語句頻度：

$\begin{matrix} \sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} \sum\limits_{j=0}^{i-1}1= \sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} \sum\limits_{j=1}^{i}1=\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} i=\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} (x-1)=S_{\lceil \sqrt{n}\ \rceil} =\frac{(\lceil \sqrt{n}\ \rceil)^{2}-\lceil \sqrt{n}\ \rceil}{2} \approx \frac{(\sqrt{n}\,)^{2} -\sqrt{n}}{2} \approx \frac{n -\sqrt{n}}{2}\\[1.5ex]\end{matrix}$

3.時間復雜度： $T(n)=O(n)$

因為是嵌套相關循環，內外層循環相關，不能分開計算

但是可以先列出來求和式的上下限，再多重求和

因為內層循環條件是 j<i?，所以 j?能取的最大值（即求和上限）是：i-1

所以內層循環的求和式上下限為

$\sum\limits_{j=0}^{i-1}$

因為外層循環條件不是以往的 i<n，而是 i*i<n

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環條件?i*i 的變化規律，將其當作數列

循環變量初始化：i=0

循環變量自增：i++

將循環變量 i 的值依次代入循環條件 i*i，探尋數列規律

$i*i=a_{1}=0\times 0=0^{2}=0 \\[1.5ex] i*i=a_{2}=1\times 1=1^{2}=1 \\[1.5ex] i*i=a_{3}=2\times 2=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] i*i=a_{x}=(x-1)\times (x-1)=(x-1)^{2} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i*i=(x-1)^{2}$

又因為循環條件是 $i*i < n$

不等式兩邊不都是整數表達式，不好計算最后一次循環的x值

所以不追求列等式，而是直接將? $i*i=(x-1)^{2}$ ?代入不等式，得

$i*i=(x-1)^{2}<n$

不等式兩邊同時開平方

$x-1<\sqrt{n}$

移項，得到循環執行次數x的范圍

$x<\sqrt{n}+1$

根據【例8.2】中的結論：

x是整數，不等式關系為? $x<f(n)$ ?，則整數x的最大值? $x_{max}=\lceil f(n) \rceil -1$

代入本題：

x是整數，不等式關系為? $x<\sqrt{n}+1$ ?，則整數x的最大值? $x_{max}=\lceil \sqrt{n}+1 \rceil -1=\lceil \sqrt{n}\ \rceil$

令求和變量 x?從1到? $\lceil \sqrt{n}\ \rceil$ ，代表循環執行? $\lceil \sqrt{n}\ \rceil$ 次

所以外層循環的求和式上下限為：

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil}$

??

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} \sum\limits_{j=0}^{i-1}1$

雙重求和可以加括號以區分

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} \sum\limits_{j=0}^{i-1}1=\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} (\sum\limits_{j=0}^{i-1}1)$

可以類比復合函數，先計算括號內的

$\sum\limits_{j=0}^{i-1}1 =\sum\limits_{j=0+1}^{i-1+1}1=\sum\limits_{j=1}^{i}1=\overbrace{1+\cdots +1}^{i} = i$

將括號內的求和式替換為計算結果，雙重求和變為?

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} (\sum\limits_{j=0}^{i-1}1)=\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} i$

注意，此時求和變量 x 與求和表達式 i 是不同符號，直接展開無意義

所以需要把?i 替換為關于求和變量 x 的表達式

前面已推導出最后一次循環（第x次循環）時

$i*i=(x-1)^{2}$

等式兩邊同時開平方

$i=x-1$

把 $i$ ?替換

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} i=\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} (x-1)$

將其展開得

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} (x-1)\\[1.5ex] =(1-1)+(2-1)+\cdots+(\lceil \sqrt{n}\ \rceil-1)\\[1.5ex] =0+1+\cdots+(\lceil \sqrt{n}\ \rceil-1)$

此時變為等差數列求和

首項? $a_{1}=0$ ，公差? $d=1$

代入等差數列求和公式?

$S_{n}=\frac{n(a_{1}+a_{n})}{2}$

得到語句頻度

$\sum\limits_{x=1}^{\lceil \sqrt{n}\ \rceil} (x-1)\\[1.5ex] =S_{\lceil \sqrt{n}\ \rceil}\\[1.5ex] =\frac{(\lceil \sqrt{n}\ \rceil)(0+\lceil \sqrt{n}\ \rceil-1)}{2}\\[1.5ex] =\frac{(\lceil \sqrt{n}\ \rceil)(\lceil \sqrt{n}\ \rceil-1)}{2}\\[1.5ex] =\frac{(\lceil \sqrt{n}\ \rceil)^{2}-\lceil \sqrt{n}\ \rceil}{2}\\[1.5ex] \approx \frac{(\sqrt{n}\,)^{2} -\sqrt{n}}{2}\\[1.5ex] \approx \frac{n -\sqrt{n}}{2}\\[1.5ex]$

解釋一下，因為? $\lceil \sqrt{n}\ \rceil$ 與? $\sqrt{n}$ ??差距很小，所以

$\lceil \sqrt{n}\ \rceil \approx \sqrt{n}$

同時平方得

$(\lceil \sqrt{n}\ \rceil)^{2} \approx (\sqrt{n}\,)^{2} \approx n$ ?

最終

$\frac{(\lceil \sqrt{n}\ \rceil)^{2}-\lceil \sqrt{n}\ \rceil}{2} \approx \frac{(\sqrt{n}\,)^{2} -\sqrt{n}}{2} \approx \frac{n -\sqrt{n}}{2}\\[1.5ex]$

省略系數和無關項后，數量級為? $n$ ，則時間復雜度為? $O(n)$

??

七、變形題

（下面是我自己想出來的一些變形題）

【變形題1】下列程序段的時間復雜度是（B）

int count=0;
for(int i=1; i*i<=n; i*=2)count++;

A． $O(n^{\frac{1}{2}})$ ? ? B． $O(log_{2}n)$ ? ? C． $O(n)$ ? ? D． $O(n log_{2}n)$

本題看著像是把【例8.1】對數階與【例10.1】根號階結合起來，但最終結果不是

因為平方只是將其指數變為2倍：? $a^{x}\times a^{x}=a^{x+x}=a^{2x}$

??

計算時間復雜度

1.基本語句：count++;

2.基本語句的語句頻度： $\sum\limits_{x=1}^{\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor}=\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor$

3.時間復雜度： $T(n)=O(log_{2}{n})$

因為本例的循環變量自增不是以往的 i++，而是 i*=2

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 i 的變化規律，將其當作數列

循環變量初始化：i=1，則首項? $a_{1}=1$

循環變量自增：i*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 i 隨著通項公式改變?

$i=a_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] i=a_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] i=a_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] i=a_{x}=2^{x-1} \\[1.5ex]$

為探尋循環條件?i*i 的變化規律，也將其當作數列

將上述循環變量 i 的值依次代入循環條件 i*i，探尋數列規律

$i*i=b_{1}=2^{0} \times 2^{0}=2^{0+0}=2^{0}=1 \\[1.5ex] i*i=b_{2}=2^{1} \times 2^{1}=2^{1+1}=2^{2}=4 \\[1.5ex] i*i=b_{3}=2^{2} \times 2^{2}=2^{2+2}=2^{4}=16 \\[1.5ex] \cdots \\[1.5ex] i*i=b_{x}=2^{x-1} \times 2^{x-1}=2^{(x-1)+(x-1)}=2^{2(x-1)} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i*i=2^{2(x-1)}$

又因為循環條件是 $i*i\leqslant n$

所以最后一次循環時 $i*i=n$ ，則

$i*i=2^{2(x-1)}=n$

等式兩邊同時取對數

$2(x-1)=log_{2}{(n)}$

等式兩邊同時除以2

$x-1=\frac{1}{2} log_{2}{(n)}$

移項，得到循環執行次數x的值

$x=\frac{1}{2} log_{2}{(n)}+1$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor$

現在就可以列求和式計算了

for循環只有1條基本語句，所以求和表達式（通項公式）是1

令求和變量 x?從1到? $\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor$ ，代表循環執行? $\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor$ 次

則語句頻度為：

$\sum\limits_{x=1}^{\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor} 1=\overbrace{1+\cdots +1}^{\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor}=\lfloor \frac{1}{2} log_{2}{(n)}+1\rfloor$

省略系數和無關項后，數量級為? $log_{2}{n}$ ，則時間復雜度為? $O(log_{2}{n})$

【變形題2】下列程序段的時間復雜度是（D）

int count=0;
for(int i=1; i<=n; i++)for(int j=1; j<=i; j*=2)count++;

A． $O(n^{\frac{1}{2}})$ ? ? B． $O(log_{2}n)$ ? ? C． $O(n)$ ? ? D． $O(n log_{2}n)$

本題看著與【例9】線性對數階類似，但內層循環條件不同

【例9】是嵌套無關循環，而本題是?嵌套相關循環

計算時間復雜度

1.基本語句：count++;

2.基本語句的語句頻度：

$\sum\limits_{i=1}^{n}\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}1 =\sum\limits_{i=1}^{n} \lfloor log_{2}{(i)}+1\rfloor \approx \sum\limits_{i=1}^{n} (log_{2}{(i)}+1) \approx \sum\limits_{i=1}^{n}log_{2}{(i)}+\sum\limits_{i=1}^{n}1\\[1.5ex] \approx log_{2}{(n!)}+n \approx n\cdot log_{2}{(n)}+(1-log_{2}{(e)})\cdot n+\frac{1}{2}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

3.時間復雜度： $T(n)=O(nlog_{2}n)$

因為是嵌套相關循環，內外層循環相關，不能分開計算

但是可以先列出來求和式的上下限，再多重求和

因為外層循環條件是 i<=n，所以 i?能取的最大值（即求和上限）是：n

所以外層循環的求和式上下限為

$\sum\limits_{i=1}^{n}$

????

因為內層循環變量自增不是以往的 j++，而是 j*=2

所以循環變量 j?不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環變量 j?的變化規律，將其當作數列

循環變量初始化：j=1，則首項? $a_{1}=1$

循環變量自增：j*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $a_{n}=a_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 j?隨著通項公式改變?

$j=a_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] j=a_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] j=a_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] j=a_{x}=2^{x-1} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$j=2^{x-1}$

又因為循環條件是 $j \leqslant i$

所以最后一次循環時 $j=i$ ，則

$j=2^{x-1}= i$

等式兩邊同時取對數

$x-1=log_{2}{(i)}$

移項，得到循環執行次數x的值

$x=log_{2}{(i)}+1$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor log_{2}{(i)}+1\rfloor$

令求和變量 x?從1到? $\lfloor log_{2}{(i)}+1\rfloor$ ，代表循環執行? $\lfloor log_{2}{(i)}+1\rfloor$ 次

所以內層循環的求和式上下限為：

$\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}$

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{i=1}^{n}\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}1$

雙重求和可以加括號以區分

$\sum\limits_{i=1}^{n}\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}1=\sum\limits_{i=1}^{n} (\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}1)$

可以類比復合函數，先計算括號內的

$\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}1=\overbrace{1+\cdots +1}^{\lfloor log_{2}{(i)}+1\rfloor} = \lfloor log_{2}{(i)}+1\rfloor$

將括號內的求和式替換為計算結果，雙重求和變為?

$\sum\limits_{i=1}^{n} (\sum\limits_{x=1}^{\lfloor log_{2}{(i)}+1\rfloor}1)=\sum\limits_{i=1}^{n}\lfloor log_{2}{(i)}+1\rfloor$

向下取整不容易計算，將其近似為

$\sum\limits_{i=1}^{n} \lfloor log_{2}{(i)}+1\rfloor \approx \sum\limits_{i=1}^{n} (log_{2}{(i)}+1)$

根據求和式的加法規則，可以拆分為

$\sum\limits_{i=1}^{n} (log_{2}{(i)}+1)=\sum\limits_{i=1}^{n}log_{2}{(i)}+\sum\limits_{i=1}^{n}1=\sum\limits_{i=1}^{n}log_{2}{(i)}+n$

下面將新求和式? $\sum\limits_{i=1}^{n}log_{2}{(i)}$ ?展開，可以看到是多個對數求和

$\sum\limits_{i=1}^{n}log_{2}{(i)}=log_{2}{(1)}+log_{2}{(2)}+\cdots+log_{2}{(n-1)}+log_{2}{(n)}$

根據對數的加法法則

$log_{a}{(M)}+log_{a}{(N)}=log_{a}{(M\times N)}$

則上述求和可以轉為

$\begin{matrix} log_{2}{(1)}+log_{2}{(2)}+\cdots+log_{2}{(n-1)}+log_{2}{(n)}=log_{2}{(1\times 2\times \cdots\times (n-1)\times n)} \end{matrix}$

因為從1乘到n可以寫作階乘n!

$1\times 2\times \cdots\times (n-1)\times n=n!$

所以替換后

$log_{2}{(1\times 2\times \cdots\times (n-1)\times n)} =log_{2}{(n!)}$

則新求和式

$\sum\limits_{i=1}^{n}log_{2}{(i)}=log_{2}{(n!)}$

則原求和式

$\sum\limits_{i=1}^{n} (log_{2}{(i)}+1)=\sum\limits_{i=1}^{n}log_{2}{(i)}+\sum\limits_{i=1}^{n}1=log_{2}{(n!)}+n$

根據斯特林公式，階乘n!的近似值為

$n!\approx \sqrt{2\pi n}\ (\frac{n}{e})^{n}$

代入得

$log_{2}{(n!)}\approx log_{2}(\sqrt{2\pi n}\ (\frac{n}{e})^{n})$

根據對數的加法法則

$log_{a}{(M\times N)}=log_{a}{(M)}+log_{a}{(N)}$

上式可拆分為

$log_{2}(\sqrt{2\pi n}\ (\frac{n}{e})^{n})=log_{2}(\sqrt{2\pi n}\,)+log_{2}((\frac{n}{e})^{n})$

根據對數的冪法則

$log_{a}{(M^{n})}=n\cdot log_{a}{(M)}$

根號是? $\frac{1}{2}$ 次冪，上式變為

$log_{2}(\sqrt{2\pi n}\,)+log_{2}((\frac{n}{e})^{n})\\[1.5ex] =log_{2}((2\pi n)^{\frac{1}{2}})+log_{2}((\frac{n}{e})^{n})\\[1.5ex] =\frac{1}{2}\cdot log_{2}{(2\pi n)}+n\cdot log_{2}{(\frac{n}{e})}$

??

將兩項分開計算：

根據對數的加法法則

$log_{a}{(M\times N)}=log_{a}{(M)}+log_{a}{(N)}$

第一項可拆分為

$\frac{1}{2}\cdot log_{2}{(2\pi n)}\\[1.5ex] =\frac{1}{2}\cdot [log_{2}(2)+log_{2}(\pi)+log_{2}(n) ]\\[1.5ex] =\frac{1}{2}\cdot[1+log_{2}(\pi)+log_{2}(n) ]$

根據對數的減法法則

$log_{a}{(\frac{M}{N})}=log_{a}{(M)}-log_{a}{(N)}$

第二項可拆分為

$n\cdot log_{2}{(\frac{n}{e})}=n\cdot [log_{2}{(n)}-log_{2}{(e)}]$

兩項相加

$\frac{1}{2}\cdot log_{2}{(2\pi n)}+n\cdot log_{2}{(\frac{n}{e})}\\[1.5ex] =\frac{1}{2}\cdot[1+log_{2}{(\pi)}+log_{2}{(n)} ]+n\cdot [log_{2}{(n)}-log_{2}{(e)}]\\[1.5ex] =\frac{1}{2}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}\cdot log_{2}{(n)}+n\cdot log_{2}{(n)}- log_{2}{(e)}\cdot n \\[1.5ex] =n\cdot log_{2}{(n)}-log_{2}{(e)}\cdot n+\frac{1}{2}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

則新求和式

$\sum\limits_{i=1}^{n}log_{2}{(i)}\\[1.5ex] =log_{2}{(n!)} \\[1.5ex] \approx n\cdot log_{2}{(n)}-log_{2}{(e)}\cdot n+\frac{1}{2}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

則原求和式

$\sum\limits_{i=1}^{n} (log_{2}{(i)}+1)\\[1.5ex] =\sum\limits_{i=1}^{n}log_{2}{(i)}+\sum\limits_{i=1}^{n}1\\[1.5ex] =log_{2}{(n!)}+n \\[1.5ex] \approx n\cdot log_{2}{(n)}-log_{2}{(e)}\cdot n+\frac{1}{2}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}+n\\[1.5ex] \approx n\cdot log_{2}{(n)}+(n-log_{2}{(e)}\cdot n)+\frac{1}{2}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}\\[1.5ex] \approx n\cdot log_{2}{(n)}+(1-log_{2}{(e)})\cdot n+\frac{1}{2}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

令常數? $c_{1}=1-log_{2}{(e)}$

令常數? $c_{2} =\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

語句頻度近似值為

$\sum\limits_{i=1}^{n} \lfloor log_{2}{(i)}+1\rfloor \approx \sum\limits_{i=1}^{n} (log_{2}{(i)}+1)\approx n\cdot log_{2}{(n)}+c_{1} n+\frac{1}{2}\cdot log_{2}{(n)}+c_{2}$

省略系數和無關項后，數量級為? $nlog_{2}n$ ，則時間復雜度為? $O(nlog_{2}n)$

?【變形題3】下列程序段的時間復雜度是（B）

int count=0;
for(int i=1; i*i<=n; i++)for(int j=1; j<=i; j*=2)count++;

A． $O(log_{2}n)$ ? ? B． $O(\sqrt{n}\, log_{2}n)$ ? ? C． $O(n)$ ? ? D． $O(n log_{2}n)$

本題看著與【變形題2】很像，但外層循環條件不同

? ?

計算時間復雜度

1.基本語句：count++;

2.基本語句的語句頻度：

$\begin{matrix} \sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}1 =\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\lfloor log_{2}{(i)}+1\rfloor \approx \sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(i)}+1) \approx \sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(x)}+1) \approx \sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)} + \sum\limits_{x=1}^{ \sqrt{n} }1 \end{matrix} \\[1.5ex] \begin{matrix} \approx log_{2}{((\sqrt{n}) !)} + \sqrt{n} \approx \frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)+ (1-log_{2}(e))\sqrt{n}+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2} \end{matrix}$

3.時間復雜度： $T(n)=O(\sqrt{n}\, log_{2}n)$

因為是嵌套相關循環，內外層循環相關，不能分開計算

但是可以先列出來求和式的上下限，再多重求和

因為外層循環條件不是以往的 i<=n，而是 i*i<=n

所以循環變量 i 不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環條件?i*i 的變化規律，將其當作數列

循環變量初始化：i=1

循環變量自增：i++

將循環變量 i 的值依次代入循環條件 i*i，探尋數列規律

$i*i=a_{1}=1\times 1=1^{2} \\[1.5ex] i*i=a_{2}=2\times 2=2^{3} \\[1.5ex] i*i=a_{3}=3\times 3=3^{2} \\[1.5ex] \cdots \\[1.5ex] i*i=a_{x}=x\times x=x^{2} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$i*i=x^{2}$

又因為循環條件是 $i*i\leqslant n$

所以最后一次循環時 $i*i=n$ ，則

$i*i=x^{2}= n$

等式兩邊同時開平方，得到循環執行次數x的值

$x=\sqrt{n}$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor \sqrt{n} \rfloor$

所以外層循環的求和式上下限為：

$\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}$

????

因為內層循環變量自增不是以往的 j++，而是 j*=2

所以循環變量 j?不能反映實際的循環執行次數

設循環的執行次數為 y?次

為探尋循環變量 j?的變化規律，將其當作數列

循環變量初始化：j=1，則首項? $b_{1}=1$

循環變量自增：j*=2，則公比? $q=2$ ，即等比數列

等比數列通項公式： $b_{n}=b_{1}q^{n-1}=1\times 2^{n-1}=2^{n-1}$

則循環變量 j?隨著通項公式改變?

$j=b_{1}=2^{1-1}=2^{0}=1 \\[1.5ex] j=b_{2}=2^{2-1}=2^{1}=2 \\[1.5ex] j=b_{3}=2^{3-1}=2^{2}=4 \\[1.5ex] \cdots \\[1.5ex] j=b_{y}=2^{y-1} \\[1.5ex]$

所以最后一次循環（第y次循環）時

$j=2^{y-1}$

又因為循環條件是 $j \leqslant i$

所以最后一次循環時 $j=i$ ，則

$j=2^{y-1}= i$

等式兩邊同時取對數

$y-1=log_{2}{(i)}$

移項，得到循環執行次數y的值

$y=log_{2}{(i)}+1$

但是循環執行次數只能是整數，所以y還要向下取整

$y=\lfloor log_{2}{(i)}+1\rfloor$

令求和變量 y?從1到? $\lfloor log_{2}{(i)}+1\rfloor$ ，代表循環執行? $\lfloor log_{2}{(i)}+1\rfloor$ 次

所以內層循環的求和式上下限為：

$\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}$

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}1$

雙重求和可以加括號以區分

$\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}1=\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor} (\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}1)$

可以類比復合函數，先計算括號內的

$\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}1=\overbrace{1+\cdots +1}^{\lfloor log_{2}{(i)}+1\rfloor} = \lfloor log_{2}{(i)}+1\rfloor$

將括號內的求和式替換為計算結果，雙重求和變為

$\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor} (\sum\limits_{y=1}^{\lfloor log_{2}{(i)}+1\rfloor}1)=\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\lfloor log_{2}{(i)}+1\rfloor$

向下取整不容易計算，將其近似為

$\sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\lfloor log_{2}{(i)}+1\rfloor \approx \sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(i)}+1)$

注意，此時求和變量 x?與求和表達式中的 i 是不同符號，直接展開無意義

所以需要把?i 替換為關于求和變量 x 的表達式

前面已推導出最后一次循環（第x次循環）時

$i*i=x^{2}$

等式兩邊同時開平方（因為 i 的初值湊巧為1，所以二者才相等）

$i=x$

把 $i$ ?替換

$\sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(i)}+1)=\sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(x)}+1)$

根據求和式的加法規則，可以拆分為

$\sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(x)}+1)=\sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)} + \sum\limits_{x=1}^{ \sqrt{n} }1=\sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)} + \sqrt{n}$

下面將新求和式? $\sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)}$ ?展開，可以看到是多個對數求和

$\sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)}=log_{2}{(1)}+log_{2}{(2)}+\cdots+log_{2}{(\sqrt{n})}$

根據對數的加法法則

$log_{a}{(M)}+log_{a}{(N)}=log_{a}{(M\times N)}$

則上述求和可以轉為

$\begin{matrix} log_{2}{(1)}+log_{2}{(2)}+\cdots+log_{2}{(\sqrt{n})}=log_{2}{(1\times 2\times \cdots\times \sqrt{n})} \end{matrix}$

因為從1乘到? $\sqrt{n}$ ?可以寫作階乘? $(\sqrt{n}\, ) !$

$1\times 2\times \cdots \times \sqrt{n}=(\sqrt{n}\, ) !$

所以替換后

$log_{2}{(1\times 2\times \cdots\times \sqrt{n}\, )} =log_{2}{((\sqrt{n}\, ) !)}$

則新求和式

$\sum\limits_{x=1}^{\sqrt{n}}log_{2}{(x)}=log_{2}{((\sqrt{n}\, ) !)}$

則原求和式

$\sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(x)}+1)=\sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)} + \sum\limits_{x=1}^{ \sqrt{n} }1=log_{2}{((\sqrt{n}\, ) !)} + \sqrt{n}$

根據斯特林公式，階乘n!的近似值為

$n!\approx \sqrt{2\pi n}\ (\frac{n}{e})^{n}$

則階乘? $(\sqrt{n}\, ) !$ ?的近似值為

$(\sqrt{n}\,) ! \approx \sqrt{2\pi \sqrt{n}}\ (\frac{\sqrt{n}}{e})^{\sqrt{n}}$

代入得

$log_{2}{((\sqrt{n}\, ) !)}\approx log_{2}(\sqrt{2\pi \sqrt{n}}\ (\frac{\sqrt{n}}{e})^{\sqrt{n}})$

根據對數的加法法則

$log_{a}{(M\times N)}=log_{a}{(M)}+log_{a}{(N)}$

上式可拆分為

$log_{2}(\sqrt{2\pi \sqrt{n}}\ (\frac{\sqrt{n}}{e})^{\sqrt{n}})=log_{2}(\sqrt{2\pi \sqrt{n}}\, )+log_{2}((\frac{\sqrt{n}}{e})^{\sqrt{n}})$

根據對數的冪法則

$log_{a}{(M^{n})}=n\cdot log_{a}{(M)}$

根號是? $\frac{1}{2}$ 次冪，上式變為

$log_{2}(\sqrt{2\pi \sqrt{n}}\, )+log_{2}((\frac{\sqrt{n}}{e})^{\sqrt{n}})\\[1.5ex] =log_{2}((2\pi \sqrt{n}\, )^{\frac{1}{2}})+log_{2}((\frac{\sqrt{n}}{e})^{\sqrt{n}})\\[1.5ex] =\frac{1}{2}\cdot log_{2}(2\pi \sqrt{n}\, )+\sqrt{n}\cdot log_{2}(\frac{\sqrt{n}}{e})\\[1.5ex]$

??

將兩項分開計算：

根據對數的加法法則、冪法則

$log_{a}{(M\times N)}=log_{a}{(M)}+log_{a}{(N)}$

$log_{a}{(M^{n})}=n\cdot log_{a}{(M)}$

第一項可拆分為

$\frac{1}{2}\cdot log_{2}(2\pi \sqrt{n}\, )\\[1.5ex] =\frac{1}{2}\cdot [log_{2}{(2)}+log_{2}{(\pi)}+log_{2}{(\sqrt{n}\, )}]\\[1.5ex] =\frac{1}{2}\cdot [1+log_{2}{(\pi)}+log_{2}{(n^{\frac{1}{2} })}]\\[1.5ex] =\frac{1}{2}\cdot [1+log_{2}{(\pi)}+\frac{1}{2} \cdot log_{2}{(n)}]$

根據對數的減法法則、冪法則

$log_{a}{(\frac{M}{N})}=log_{a}{(M)}-log_{a}{(N)}$

$log_{a}{(M^{n})}=n\cdot log_{a}{(M)}$

第二項可拆分為

$\sqrt{n}\cdot log_{2}(\frac{\sqrt{n}}{e})\\[1.5ex] =\sqrt{n}\cdot [log_{2}(\sqrt{n}\, )-log_{2}(e)]\\[1.5ex] =\sqrt{n}\cdot [log_{2}(n^{\frac{1}{2} })-log_{2}(e)]\\[1.5ex] =\sqrt{n}\cdot [\frac{1}{2}\cdot log_{2}(n)-log_{2}(e)]$

兩項相加

$\frac{1}{2}\cdot log_{2}(2\pi \sqrt{n}\, )+\sqrt{n}\cdot log_{2}(\frac{\sqrt{n}}{e})\\[1.5ex] =\frac{1}{2}\cdot [1+log_{2}{(\pi)}+\frac{1}{2} \cdot log_{2}{(n)}]+\sqrt{n}\cdot [\frac{1}{2}\cdot log_{2}(n)-log_{2}(e)]\\[1.5ex] =\frac{1}{2}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)-log_{2}(e)\cdot \sqrt{n}\\[1.5ex] =\frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)-log_{2}(e)\cdot \sqrt{n}+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

則新求和式

$\sum\limits_{x=1}^{\sqrt{n}}log_{2}{(x)}\\[1.5ex] =log_{2}{((\sqrt{n}\, ) !)}\\[1.5ex] \approx \frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)-log_{2}(e)\cdot \sqrt{n}+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

則原求和式

$\sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(x)}+1)\\[1.5ex] =\sum\limits_{x=1}^{ \sqrt{n} } log_{2}{(x)} + \sum\limits_{x=1}^{ \sqrt{n} }1\\[1.5ex] =log_{2}{((\sqrt{n}\, ) !)} + \sqrt{n}\\[1.5ex] \approx \frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)-log_{2}(e)\cdot \sqrt{n}+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}+\sqrt{n}\\[1.5ex] \approx \frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)+ (\sqrt{n}-log_{2}(e)\cdot \sqrt{n}\, )+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}\\[1.5ex] \approx \frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)+ (1-log_{2}(e))\cdot \sqrt{n}+\frac{1}{4}\cdot log_{2}{(n)}+\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

令常數? $c_{1}=1-log_{2}{(e)}$

令常數? $c_{2} =\frac{1}{2}\cdot log_{2}{(\pi)}+\frac{1}{2}$

語句頻度近似值為

$\begin{matrix} \sum\limits_{x=1}^{\lfloor \sqrt{n} \rfloor}\lfloor log_{2}{(i)}+1\rfloor \approx \sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(i)}+1)\approx \sum\limits_{x=1}^{ \sqrt{n} } (log_{2}{(x)}+1)\approx \frac{1}{2}\cdot \sqrt{n} \cdot log_{2}(n)+ c_{1}\sqrt{n}+\frac{1}{4}\cdot log_{2}{(n)}+c_{2} \end{matrix}$

省略系數和無關項后，數量級為? $\sqrt{n}\, log_{2}n$ ，則時間復雜度為? $O(\sqrt{n}\, log_{2}n)$

? ??

【變形題4】下列程序段的時間復雜度是（C）

int count=0;
for(int i=1; i<=n; i++)for(int j=1; j*j<=i; j++)count++;

A． $O(n^{\frac{1}{2}})$ ? ? B． $O(n)$ ? ? C． $O(n^{\frac{3}{2}})$ ? ? D． $O(n^{2})$

乍一看，像是把【2025年第 1 題】內外顛倒了，實則不然

計算時間復雜度

1.基本語句：count++;

2.基本語句的語句頻度： $\begin{matrix} \sum\limits_{i=1}^{n} \sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor} 1=\sum\limits_{i=1}^{n} \lfloor \sqrt{i} \rfloor \approx \sum\limits_{i=1}^{n} \sqrt{i} \approx \int_{?{1}}^{?{n}}\sqrt{x}\ dx + \frac{\sqrt{1} + \sqrt{n}}{2} \approx \frac{2}{3}n^{\frac{3}{2}}+\frac{1}{2}n^{\frac{1}{2}}-\frac{1}{6}\\[1.5ex] \end{matrix}$

3.時間復雜度： $T(n)=O(n^{\frac{3}{2}})$

因為是嵌套相關循環，內外層循環相關，不能分開計算

但是可以先列出來求和式的上下限，再多重求和

因為外層循環條件是 i<=n，所以 i?能取的最大值（即求和上限）是：n

所以外層循環的求和式上下限為

$\sum\limits_{i=1}^{n}$

因為內層循環條件不是以往的 j<=i，而是 j*j<=i

所以循環變量 j?不能反映實際的循環執行次數

設循環的執行次數為 x 次

為探尋循環條件 j*j?的變化規律，將其當作數列

循環變量初始化：j=1

循環變量自增：j++

將循環變量 j?的值依次代入循環條件 j*j，探尋數列規律

$j*j=a_{1}=1\times 1=1^{2}=1 \\[1.5ex] j*j=a_{2}=2\times 2=2^{2}=4 \\[1.5ex] j*j=a_{3}=3\times 3=3^{2}=9 \\[1.5ex] \cdots \\[1.5ex] j*j=a_{x}=x\times x=x^{2} \\[1.5ex]$

所以最后一次循環（第x次循環）時

$j*j=x^{2}$

又因為循環條件是 $j*j \leqslant i$

所以最后一次循環時 $j*j=i$ ，則

$j*j=x^{2}=i$

等式兩邊同時開平方，得到循環執行次數x的值

$x=\sqrt{i}$

但是循環執行次數只能是整數，所以x還要向下取整

$x=\lfloor \sqrt{i} \rfloor$

令求和變量 x?從1到? $\lfloor \sqrt{i} \rfloor$ ，代表循環執行? $\lfloor \sqrt{i} \rfloor$ 次

所以內層循環的求和式上下限為：

$\sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor}$

??

二層循環體只有1條基本語句，所以求和表達式（通項公式）是1

二層循環（雙重循環）計算語句頻度需要寫成雙重求和

$\sum\limits_{i=1}^{n} \sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor} 1$

雙重求和可以加括號以區分

$\sum\limits_{i=1}^{n} \sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor} 1=\sum\limits_{i=1}^{n} (\sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor} 1)$

可以類比復合函數，先計算括號內的

$\sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor}1=\overbrace{1+\cdots +1}^{\lfloor \sqrt{i} \rfloor} = \lfloor \sqrt{i} \rfloor$

將括號內的求和式替換為計算結果，雙重求和變為

$\sum\limits_{i=1}^{n} (\sum\limits_{x=1}^{\lfloor \sqrt{i} \rfloor} 1)=\sum\limits_{i=1}^{n} \lfloor \sqrt{i} \rfloor$

向下取整不容易計算，將其近似為

$\sum\limits_{i=1}^{n} \lfloor \sqrt{i} \rfloor \approx \sum\limits_{i=1}^{n} \sqrt{i}$

再展開，可以看到是多個根號求和

$\sum\limits_{i=1}^{n} \sqrt{i}=\sqrt{1}+\cdots +\sqrt{n}$

既不是等差數列也不是等比數列，這怎么辦呢？

將根號看作? $\frac{1}{2}$ ?次冪，上式變為

$\sum\limits_{i=1}^{n} i^{\frac{1}{2}}=1^{\frac{1}{2}}+\cdots +n^{\frac{1}{2}}$

等冪求和可以用歐拉—麥克勞林公式近似計算

（歐拉—麥克勞林公式是連接離散求和與連續積分的橋梁）

歐拉—麥克勞林公式

$\begin{matrix} \sum\limits_{?{i=a}}^{?{b}}f(i) = \int_{?{a}}^{?{b}}f(x)dx + \frac{f(a) + f(b)}{2} + \sum\limits_{?{k=1}}^{?{m }}\frac{?{B_{?{2k}}}}{?{(2k)!}}\left[f^{?{(2k-1)}}(b) - f^{?{(2k-1)}}(a)\right] + R_{m} \end{matrix}$

* 修正項： $\sum\limits_{?{k=1}}^{m}\frac{?{B_{?{2k}}}}{?{(2k)!}}\left[f^{?{(2k-1)}}(b) - f^{?{(2k-1)}}(a)\right]$ ，其中? $B_{2k}$ ?是伯努利數（如 $B_{2}=\frac{1}{6}$ ， $B_{4}=-\frac{1}{30}$ ）

* 剩余項： $R_{m}= \frac{(-1)^{m+1} }{(2m)!}\int_{a}^{b} B_{2m}( \{ x \} ) f^{(2m)}(x) dx$ ?，其中? $\{x \}=x-\lfloor x\rfloor$ ，?代表取小數（保留小數部分，忽略整數部分）?

只作近似計算，忽略修正項和剩余項，上式約等于

$\sum\limits_{?{i=a}}^{?{b}}f(i) \approx \int_{?{a}}^{?{b}}f(x)dx + \frac{f(a) + f(b)}{2}$

將? $a=1,\ b=n,\ f(i)=i^{\frac{1}{2}}$ ?代入得語句頻度

$\sum\limits_{i=1}^{n} i^{\frac{1}{2}} \approx \int_{?{1}}^{?{n}}x^{\frac{1}{2}} dx + \frac{1^{\frac{1}{2}} + n^{\frac{1}{2}}}{2} \\[1.5ex] \approx \int_{?{1}}^{?{n}}x^{\frac{1}{2}} dx+\frac{n^{\frac{1}{2}}}{2}+\frac{1}{2} \\[1.5ex] \approx \frac{ x^{\frac{3}{2}} }{\frac{3}{2}} |_{1}^{n}+\frac{1}{2}n^{\frac{1}{2}}+\frac{1}{2} \\[1.5ex] \approx \frac{2}{3}x^{\frac{3}{2}}|_{1}^{n}+\frac{1}{2}n^{\frac{1}{2}}+\frac{1}{2}\\[1.5ex] \approx \frac{2}{3}(n^{\frac{3}{2}}-1^{\frac{3}{2}})+\frac{1}{2}n^{\frac{1}{2}}+\frac{1}{2}\\[1.5ex] \approx \frac{2}{3}n^{\frac{3}{2}}-\frac{2}{3}+\frac{1}{2}n^{\frac{1}{2}}+\frac{1}{2}\\[1.5ex] \approx \frac{2}{3}n^{\frac{3}{2}}+\frac{1}{2}n^{\frac{1}{2}}-\frac{1}{6}\\[1.5ex]$

省略系數和無關項后，數量級為? $n^{\frac{3}{2}}$ ，則時間復雜度為? $O(n^{\frac{3}{2}})$

????

八、遞歸題

?【遞歸題1 - 2026王道數據結構第11題】下列程序段的時間復雜度是（C）

int Func(int n)
{if(n==1) return 1;else return 2*Func(n/2)+n;
}

A． $O(n)$ ? ? B． $O(nlog_{2}n)$ ? ? C． $O(log_{2}n)$ ? ? D． $O(n^{2})$

*為了方便描述，后續均用f(n)指代Func(n)

計算時間復雜度

1.基本語句：

return 1;

return 2*f(n/2)+n;

2.基本語句的語句頻度： $log_{2}(n)+1$

3.時間復雜度： $T(n)=O(log_{2}n)$

遞歸函數無法按常規方式計算語句頻度

但是可以轉換思路，將遞歸過程模擬為二叉樹

一個遞歸函數當作二叉樹的一個節點

函數f(n)遞歸調用的是f(n/2)

從二叉樹的視角來看，就是該節點連接n/2層的一個孩子

所以每個節點（不算葉子節點）都只有一個孩子，最終得到"單叉"的二叉樹

其實這棵"單叉"的二叉樹就是線性表（或稱二叉樹退化為線性表）

縱向可能看不出來是線性表，改成橫向就一目了然

例如：f(8)的遞歸二叉樹（退化為線性表）如下圖

因為函數參數n定義為int類型

如果調用的實參不是整數，則會對其向下取整

所以調用 $f(\frac{n}{2})$ ，實際上是調用 $f( \left \lfloor \frac{n}{2} \right \rfloor)$

為了簡化分析，僅考慮偶數情況，避免向下取整造成影響

當n為偶數時，f(n)遞歸過程如下

$f(n)\rightarrow f(\frac{n}{2})\rightarrow f(\frac{n}{4})\rightarrow \cdots \rightarrow f(1)$

從前往后看，當作數列

$n,\ \frac{n}{2},\ \frac{n}{4},\ \cdots,\ 1$

則為等比數列

$a_{1}=n,\ a_{2}=\frac{n}{2},\ a_{3}=\frac{n}{4},\ \cdots,\ a_{m}=1$

首項? $a_{1}=n$ ，公比 $q=\frac{1}{2}$

等比數列通項公式? $a_{m}=a_{1}q^{m-1}=n\times (\frac{1}{2})^{m-1}$

代入最后一項?

$a_{m}=n\times (\frac{1}{2})^{m-1}=1$

等式兩邊同時除以n

$(\frac{1}{2})^{m-1}=\frac{1}{n}$

倒數可以寫成-1次冪

$(2^{-1})^{m-1}=n^{-1}$

將等式左邊展開

$2^{-m+1}=n^{-1}$

等式兩邊同時取對數

$-m+1=log_{2}(n^{-1})$

根據對數的冪法則

$log_{a}{(M^{n})}=n\cdot log_{a}{(M)}$

將冪次提出

$-m+1=-log_{2}(n)$

等式兩邊同時取相反數

$m-1=log_{2}(n)$

移項得

$m=log_{2}(n)+1$

數列從 $a_{1}$ ?到? $a_{m}$ 共m項，則遞歸過程有m層

又因為退化為線性表，所以總節點數就是 $m=log_{2}(n)+1$

再看函數體，無論進 if 還是進 else，都只會執行1條語句

所以遞歸函數內基本語句的語句頻度是1

所以?語句頻度之和 = 線性表總節點數? $=log_{2}(n)+1$

省略系數和無關項后，數量級為? $log_{2}n$ ，則時間復雜度為? $O(log_{2}n)$

???

或者使用主定理（Master定理）進行推導

主定理（Master定理）

一、遞歸函數的時間復雜度滿足以下遞推公式：

$T(n)= \left\{\begin{matrix} a\cdot T(\frac{n}{b})+f(n)&,\ n>n_{0}\\[1.5ex] O(1)&,\ n=n_{0} \end{matrix}\right.$ ? （其中 $a\geqslant 1$ 且 $b>1$ ， $n_{0}$ 是遞歸結束條件）

$n$ ：問題規模

$a$ ：每次遞歸調用的子問題數量（即子遞歸調用次數）

$\frac{n}{b}$ ：每個子問題的規模（必須相等）

$f(n)$ ：非遞歸操作的語句頻度

? ?

令非遞歸操作的時間復雜度? $O(f(n))=O(n^{d})$

這是簡化分析，假定其時間復雜度為常見的冪函數，方便后續只比較指數? $d$

但如果時間復雜度確實不是冪函數，則需要整體比較

將? $f(n)$ ?用時間復雜度? $O(n^{d})$ ?來近似估計，則遞推公式變為

$T(n)= \left\{\begin{matrix} a\cdot T(\frac{n}{b})+O(n^{d})&,\ n>n_{0}\\[1.5ex] O(1)&,\ n=n_{0} \end{matrix}\right.$ ? （其中 $a\geqslant 1$ 且 $b>1$ ， $n_{0}$ 是遞歸結束條件）

遞歸操作的時間復雜度經復雜推導（過程略）可近似為? $O(n^{log_{b}\,a})$ ?

????

二、應用條件

1、子問題規模相等?：原問題需被分割成規模相同的子問題（如歸并排序的 $\frac{n}{2}$ 分割）

2、非遞歸操作的時間復雜度： $O(n^{d})$ 中的? $d$ 必須為常數，不能隨? $n$ 變化

???

三、主定理判斷時間復雜度的三種情況

實際上是看遞歸操作? $O(n^{log_{b}\,a})$ ?和非遞歸操作? $O(n^{d})$ ?哪個占主導

1、遞歸主導

當 $d<log_{b}\,a$ 時，遞歸操作耗時占主導，則遞歸函數的時間復雜度 $T(n)=O(n^{log_{b}\,a})$

2、平衡狀態

當 $d=log_{b}\,a$ 時，遞歸與非遞歸操作耗時相當，則遞歸函數的時間復雜度 $T(n)=O(n^{d}\,log\,n)$

3、非遞歸主導

當 $d>log_{b}\,a$ 時，非遞歸操作耗時占主導

還需滿足條件：存在常數? $c\ (c<1)$ ，使得不等式? $a\cdot f(\frac{n}{b}) \leqslant c \cdot f(n)$ 成立

則遞歸函數的時間復雜度 $T(n)=O(n^{d})$

再把代碼貼過來，對本題進行分析

int Func(int n)
{if(n==1) return 1;else return 2*Func(n/2)+n;
}

*為了方便描述，后續均用f(n)指代Func(n)

肯定有人一上來就直接列式

$T(n)= \left\{\begin{matrix} 2T(\frac{n}{2})+O(n)&,\ n>1\\[1.5ex] O(1)&,\ n=1\end{matrix}\right.$

殊不知中了出題人的圈套，把表達式求值和時間復雜度混為一談了

? ? ?

下面從頭開始分析

1、先看子問題數量： $a$

其實子問題數量就是子遞歸的調用次數

當前遞歸函數f(n)只調用一次子遞歸f(n/2)，所以子問題數量 $a=1$ ，滿足條件? $a \geqslant 1$

有人看到 2*f(n/2) 可能會誤認為子問題數量 $a=2$

這就是將函數返回值和函數調用混淆了

2*f(n/2) 只是讓函數返回值參與運算，僅調用了一次子遞歸f(n/2)

假設當前子遞歸f(n/2)的返回值是4，則 2f(n/2)=24=8

如果要調用兩次子遞歸得把f(n/2)寫兩遍，比如 2f(n/2)f(n/2)

2、再看子問題規模： $\frac{n}{b}$

從子遞歸調用f(n/2)可以看出子問題規模是? $\frac{n}{2}$ ?，則? $b=2$ ，滿足條件? $b>1$

? ?

3、最后看非遞歸操作的時間復雜度： $O(n^{d})$

看函數體，無論進 if 還是進 else，都只會執行1條非遞歸操作語句

所以非遞歸操作的語句頻度是1，數量級為1，時間復雜度為 $O(1)=O(n^{0})$ ，則? $d=0$

有人看到 +n 可能會誤認為非遞歸操作的時間復雜度是? $O(n)$

這就是將變量運算?和語句頻度?混淆了

2*Func(n/2)+n 這個加法運算整體只是1條語句，其語句頻度是1

如果要實現非遞歸操作的時間復雜度是? $O(n)$ ?，得把 +n 放到循環里面，比如

sum=2*Func(n/2);

for(i=1; i<=n; i++)?{ sum+=n;?}

return sum;

通過上面的分析，得到正確的遞推公式為

$T(n)= \left\{\begin{matrix} T(\frac{n}{2})+O(1)&,\ n>1\\[1.5ex] O(1)&,\ n=1\end{matrix}\right.$

此時? $a=1,\ b=2,\ d=0$ ，則? $log_{b}\,a=log_{2}\,1=0$ ?

所以? $d=log_{b}\,a=0$ ，滿足第二種情況（平衡狀態）

則遞歸函數的時間復雜度 $T(n)=O(n^{d}\,log\,n)=O(n^{0}\,log\,n)=O(log\,n)$

因為對數階可以省略底數，所以兩種方式推導出的時間復雜度相同：? $O(log_{2}n)=O(log\,n)$

????

???

?【遞歸題2】下列程序段的時間復雜度是（C）

double f(int n)
{if(n==1) return 1;else{int i;double count=0;for(i=1; i<=n; i++){count+=f(n-1);}return count; }
}

A． $O(n)$ ? ? B． $O(n^{2})$ ? ? C． $O(2^{n})$ ? ? D． $O(n!)$

計算時間復雜度

1.基本語句：

return 1;

count+=f(n-1);

2.基本語句的語句頻度： $\sum\limits_{i=1}^{n} A_{n}^{i}=\sum\limits_{i=1}^{n}\frac{n!}{(n-i)!}=n!\sum\limits_{i=1}^{n}\frac{1}{(n-i)!}=n!\sum\limits_{k=0}^{n-1}\frac{1}{k!}\approx n!\cdot e \approx e\cdot n!$

3.時間復雜度： $T(n)=O(n!)$

遞歸函數無法按常規方式計算語句頻度

但是可以轉換思路，將遞歸過程模擬為樹（這里就不是二叉樹了，而是n叉樹）

一個遞歸函數當作樹的一個節點

本題遞歸過程為

$f(n)\rightarrow f(n-1)\rightarrow f(n-2)\rightarrow \cdots \rightarrow f(2) \rightarrow f(1)$

則遞歸樹共有n層

f(n)是遞歸樹的根結點，則第1層的節點數為： $1$

f(n)通過循環遞歸調用n次 f(n-1)，也就是n個 f(n-1)

從樹的視角來看，就是該節點連接第2層的n個孩子，則第2層節點數為： $1\times n=n$

對于這 n 個f(n-1) ，其中每個f(n-1)通過循環遞歸調用n-1次 f(n-2)，也就是n-1個 f(n-2)

從樹的視角來看，就是第2層的每個節點都連接第3層的n-1個孩子，則第3層節點數為： $n\times (n-1)$

如下圖所示

??????

為探尋節點數的規律，將 {節點數} 當作數列

第1層：根節點，節點數為? $a_{1}=1$

第2層：節點數為? $a_{2}=1\times n=n$

第3層：節點數為? $a_{3}=n\times (n-1)$

第4層：節點數為? $a_{4}=n\times (n-1) \times (n-2)$

第5層：節點數為? $a_{5}=n\times (n-1) \times (n-2) \times (n-3)$

……

第n層：節點數為? $a_{n}= n\times (n-1) \times (n-2) \times (n-3)\times \cdots \times 2$ ?

既不是等差數列也不是等比數列，這怎么辦呢？

可以看到節點數從n逐漸累乘至2，有沒有想到什么？

其實就是高中學過的排列數

$A_{n}^{m}=\frac{n!}{(n-m)!}=n\times (n-1) \times (n-2)\times \cdots \times (n-m+1)$

所以{節點數} 數列的規律可以用排列數表示

第1層：根節點，節點數為? $a_{1}=1=\frac{n!}{(n-0)!}=A_{n}^{0}$

第2層：節點數為? $a_{2}=1\times n=n=\frac{n!}{(n-1)!}=A_{n}^{1}$

第3層：節點數為? $a_{3}=n\times (n-1)=\frac{n!}{(n-2)!}=A_{n}^{2}$

第4層：節點數為? $a_{4}=n\times (n-1) \times (n-2)=\frac{n!}{(n-3)!}=A_{n}^{3}$

第5層：節點數為? $a_{5}=n\times (n-1) \times (n-2) \times (n-3)=\frac{n!}{(n-4)!}=A_{n}^{4}$

……

第n層：節點數為? $\begin{matrix} a_{n}=n\times (n-1) \times (n-2) \times (n-3)\times \cdots \times 2=\frac{n!}{(n-(n-1))!}=A_{n}^{n-1} \end{matrix}$

再看函數體

①進 if 時，對應第n層的葉子節點f(1)

只執行1條語句，節點語句頻度為1

②進else時，對應其他層的節點

進入for循環，for循環內執行非遞歸的加法語句，循環幾次就執行幾次

所以節點語句頻度=循環次數，循環次數隨問題規模改變

為探尋循環次數的規律，將 {循環次數} 當作數列

第1層：對應f(n)，問題規模為n，循環次數為? $b_{1}=n$

第2層：對應f(n-1)，問題規模為n-1，循環次數為? $b_{2}=n-1$

第3層：對應f(n-2)，問題規模為n-2，循環次數為? $b_{3}=n-2$

第4層：對應f(n-3)，問題規模為n-3，循環次數為? $b_{4}=n-3$

第5層：對應f(n-4)，問題規模為n-4，循環次數為? $b_{5}=n-4$

……

第n-1層：對應f(2)，問題規模為2，循環次數為? $b_{n-1}=2$

（為什么不寫第n層？因為第n層對應f(1)，進的是if，前面已得出節點語句頻度為1）

可以看出?{循環次數} 數列是等差數列

首項? $b_{1}=n$ ，公差? $d=-1$

等差數列通項公式? $b_{m}=b_{1}+(m-1)d=n+(m-1)(-1)=n+1-m$

所以節點語句頻度=循環次數 $=n+1-m$ ? （其中m是當前層數）

????

前面我們已經推導出每層的節點數，這里又推導出節點語句頻度，則

當前層語句頻度=當前層節點數 x 當前層節點語句頻度=當前層節點數 x 當前層循環次數（即 $c_{n}=a_{n}\times b_{n}$ ）

為探尋當前層語句頻度的規律，將 {當前層語句頻度} 當作數列

第1層：當前層語句頻度為

$c_{1}=a_{1}\times b_{1}=1\times (n+1-1)=1\times n=n=\frac{n!}{(n-1)!}=A_{n}^{1}$

第2層：當前層語句頻度為

$c_{2}=a_{2}\times b_{2}=n \times (n+1-2) = n\ \times (n-1) =\frac{n!}{(n-2)!}=A_{n}^{2}$

第3層：當前層語句頻度為?

$\begin{matrix} c_{3}=a_{3}\times b_{3}=n\times (n-1)\times (n+1-3)=n\times (n-1)\times (n-2)=\frac{n!}{(n-3)!}=A_{n}^{3} \end{matrix}$

第4層：當前層語句頻度為?

$c_{4}=a_{4}\times b_{4}\\[1.5ex] =n\times (n-1) \times (n-2) \times (n+1-4)\\[1.5ex] =n\times (n-1) \times (n-2) \times (n-3)=\frac{n!}{(n-4)!}=A_{n}^{4}$

第5層：當前層語句頻度為?

$c_{5}=a_{5}\times b_{5}\\[1.5ex] =n\times (n-1) \times (n-2) \times (n-3) \times (n+1-5)\\[1.5ex] =n\times (n-1) \times (n-2) \times (n-3) \times (n-4)=\frac{n!}{(n-5)!}=A_{n}^{5}$

……

第n-1層：當前層語句頻度為

? $c_{n-1}=a_{n-1}\times b_{n-1}\\[1.5ex] =n\times (n-1) \times (n-2) \times (n-3)\times (n-4)\times \cdots \times [n+1-(n-1)]\\[1.5ex] =n\times (n-1) \times (n-2) \times (n-3)\times (n-4)\times \cdots \times 2=\frac{n!}{(n-(n-1))!}=A_{n}^{n-1}$

第n層：當前層語句頻度為（對應 if 情況，直接代入1）

$c_{n}=a_{n}\times b_{n}\\[1.5ex] =n\times (n-1) \times (n-2) \times (n-3)\times (n-4)\times \cdots \times 2 \times 1=\frac{n!}{(n-n)!}=A_{n}^{n}$

求整個遞歸函數的總語句頻度，就是將第1層到第n層的當前層語句頻度相加

相當于對 {當前層語句頻度} 這個數列求和

$S_{n}=\sum\limits_{i=1}^{n} A_{n}^{i}$

用階乘表示為

$\sum\limits_{i=1}^{n} A_{n}^{i}=\sum\limits_{i=1}^{n}\frac{n!}{(n-i)!}$

這里的 n! 與求和變量 i 無關，相當于常數，可以將其提出

$\sum\limits_{i=1}^{n}\frac{n!}{(n-i)!}=n!\sum\limits_{i=1}^{n}\frac{1}{(n-i)!}$

為了簡化分母表示，設? $k=n-i$

因為 i 的變化規律是

$1,2,3,\cdots ,(n-1),n$

所以 k 的變化規律是

$(n-1),(n-2),(n-3),\cdots ,(n-(n-1)), (n-n)\\[1.5ex] =(n-1),(n-2),(n-3),\cdots ,1,0$

因為有加法交換律，所以求和變量從n-1到0 與從0到n-1 的求和結果相同

將上式改為用求和變量 k 表示的新求和式

$n!\sum\limits_{i=1}^{n}\frac{1}{(n-i)!}=n!\sum\limits_{k=0}^{n-1}\frac{1}{k!}$

《高等數學》學過自然指數函數的麥克勞林展開為

$e^{x}=\frac{x^{0}}{0!}+\frac{x^{1}}{1!}+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\frac{x^{4}}{4!}+\cdots=\sum\limits_{k=0}^{\infty}\frac{x^{k}}{k!}$

當? $x=1$ ?時，即為自然對數底e

$e=e^{1}=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+\cdots=\sum\limits_{k=0}^{\infty}\frac{1}{k!}$

當問題規模(n)?的取值很大時，可近似為

$\sum\limits_{k=0}^{n-1}\frac{1}{k!} \approx \sum\limits_{k=0}^{\infty}\frac{1}{k!} \approx e$

最終遞歸函數的總語句頻度近似為

$n!\sum\limits_{k=0}^{n-1}\frac{1}{k!} \approx n!\cdot e \approx e\cdot n!$

省略系數和無關項后，數量級為? $n!$ ，則時間復雜度為? $O(n!)$

$O(n!)$ ?可以稱作階乘階，將其與指數階? $O(2^{n})$ ?進行比較

可以看到? $n!$ ?和? $2^{n}$ ?這兩個函數在第一象限有兩個交點

一個交點在? $(0,1)$ ?

另一個交點在? $n \in[3,4]$ ?區間內

在第二次相交后， $n!$ ?的增長速率明顯要比? $2^{n}$ ?快?

所以當問題規模(n)趨于無窮大時： $O(n!)>O(2^{n})$

或者嘗試使用主定理（Master定理）進行推導

再把代碼貼過來，對本題進行分析

double f(int n)
{if(n==1) return 1;else{int i;double count=0;for(i=1; i<=n; i++){count+=f(n-1);}return count; }
}

下面從頭開始分析

1、先看子問題數量： $a$

其實子問題數量就是子遞歸的調用次數

當前遞歸函數f(n)在for循環中調用n次子遞歸f(n-1)，所以子問題數量 $a=n$ ，滿足條件? $a \geqslant 1$

? ???

2、再看子問題規模： $\frac{n}{b}$

從子遞歸調用f(n-1)可以看出子問題規模是? $n-1$ ?，此時可以當作 $b=1$ ，不滿足條件? $b>1$

所以不能使用主定理

3、最后看非遞歸操作的時間復雜度： $O(n^{d})$

進 if 時，對應第n層的葉子節點f(1)

只執行1條語句，節點語句頻度為1，數量級為1，時間復雜度為 $O(1)=O(n^{0})$ ，此時 $d=0$

進else時，對應其他層的節點

進入for循環，for循環內執行非遞歸的加法語句，循環幾次就執行幾次

所以語句頻度=循環次數，循環次數隨問題規模改變

初始節點語句頻度為n，數量級為n，時間復雜度為 $O(n)=O(n^{1})$ ，此時 $d=1$

雖然不能使用主定理，但是我們可以把遞推公式寫出來

$T(n)= \left\{\begin{matrix} nT(n-1)+O(n)&,\ n>1\\[1.5ex] O(1)&,\ n=1\end{matrix}\right.$

（下面使用遞推公式進行不嚴謹的推導）

按問題規模減小，列出時間復雜度

$T(n)= nT(n-1)+O(n)\\[1.5ex] T(n-1)= (n-1)T(n-2)+O(n-1)\\[1.5ex] T(n-2)= (n-2)T(n-3)+O(n-2)\\[1.5ex] \cdots \\[1.5ex] T(2)= 2T(1)+O(2)\\[1.5ex] T(1)=O(1)$

將上述時間復雜度逐個代入T(n)

$T(n)= nT(n-1)+O(n)\\[1.5ex] \begin{matrix} = n((n-1)T(n-2)+O(n-1))+O(n) \end{matrix} \\[1.5ex] \begin{matrix} = n((n-1)((n-2)T(n-3)+O(n-2))+O(n-1))+O(n) \end{matrix} \\[1.5ex] \begin{matrix} \cdots \end{matrix} \\[1.5ex] \begin{matrix} = n((n-1)((n-2)((n-3)\cdots (2T(1)+O(2)) +\cdots +O(n-3))+O(n-2))+O(n-1))+O(n) \end{matrix} \\[1.5ex] \begin{matrix} = n((n-1)((n-2)((n-3)\cdots (2O(1)+O(2)) +\cdots +O(n-3))+O(n-2))+O(n-1))+O(n) \end{matrix} \\[1.5ex]$

將上式拆開，改用階乘表示

$\begin{matrix} n((n-1)((n-2)((n-3)\cdots (2O(1)+O(2)) +\cdots +O(n-3))+O(n-2))+O(n-1))+O(n) \end{matrix} \\[1.5ex] \begin{matrix} = n(n-1)((n-2)((n-3)\cdots (2O(1)+O(2)) +\cdots +O(n-3))+O(n-2))+n\cdot O(n-1)+O(n) \end{matrix} \\[1.5ex] \begin{matrix} = n(n-1)(n-2)((n-3)\cdots (2O(1)+O(2)) +\cdots +O(n-3))+n\cdot (n-1)\cdot O(n-2)+n\cdot O(n-1)+O(n) \end{matrix} \\[1.5ex] \begin{matrix} = n(n-1)(n-2)(n-3)\cdots (2O(1)+O(2)) +\cdots +n\cdot (n-1)\cdot (n-2)\cdot O(n-3)+ n\cdot (n-1)\cdot O(n-2)+n\cdot O(n-1)+O(n) \end{matrix} \\[1.5ex] \begin{matrix} =\frac{n!}{1!}\cdot O(1)+ \frac{n!}{2!}\cdot O(2)+\cdots+\frac{n!}{(n-3)!}\cdot O(n-3) +\frac{n!}{(n-2)!}\cdot O(n-2) +\frac{n!}{(n-1)!}\cdot O(n-1)+\frac{n!}{n!}\cdot O(n) \end{matrix} \\[1.5ex]$

假設時間復雜度可以有如下運算規則（其中n是問題規模，c是常數）

? $n\cdot O(1)=O(n)\\[1.5ex] n!\cdot O(1)=O(n!)\\[1.5ex] c\cdot O(1)=O(c)=O(1)\\[1.5ex] c\cdot O(n)=O(c\cdot n)=O(n)\\[1.5ex] c\cdot O(n!)=O(c\cdot n!)=O(n!)\\[1.5ex]$

則上式變為

$\begin{matrix} \frac{n!}{1!}\cdot O(1)+ \frac{n!}{2!}\cdot O(2)+\cdots+\frac{n!}{(n-3)!}\cdot O(n-3) +\frac{n!}{(n-2)!}\cdot O(n-2) +\frac{n!}{(n-1)!}\cdot O(n-1)+\frac{n!}{n!}\cdot O(n) \end{matrix} \\[1.5ex] \begin{matrix} =\frac{n!}{1!}\cdot 1\cdot O(1)+ \frac{n!}{2!}\cdot 2\cdot O(1)+\cdots +\frac{n!}{(n-3)!}\cdot (n-3)\cdot O(1)+\frac{n!}{(n-2)!}\cdot (n-2)\cdot O(1) +\frac{n!}{(n-1)!}\cdot (n-1)\cdot O(1)+\frac{n!}{n!}\cdot n \cdot O(1) \end{matrix} \\[1.5ex] \begin{matrix} =\frac{n!}{0!}\cdot O(1)+ \frac{n!}{1!}\cdot O(1)+\cdots+\frac{n!}{(n-4)!}\cdot O(1) +\frac{n!}{(n-3)!}\cdot O(1) +\frac{n!}{(n-2)!}\cdot O(1)+\frac{n!}{(n-1)!}\cdot O(1) \end{matrix} \\[1.5ex] \begin{matrix} =(\frac{n!}{0!}+ \frac{n!}{1!}+\cdots+\frac{n!}{(n-4)!} ++\frac{n!}{(n-3)!}+\frac{n!}{(n-2)!}+\frac{n!}{(n-1)!} )\cdot O(1) \end{matrix}\\[1.5ex] \begin{matrix} =(\sum\limits_{k=0}^{n-1}\frac{n!}{k!})\cdot O(1) \end{matrix}\\[1.5ex] \begin{matrix} =(n!\sum\limits_{k=0}^{n-1}\frac{1}{k!})\cdot O(1) \end{matrix}\\[1.5ex] \begin{matrix} =n!\cdot O(1) \cdot \sum\limits_{k=0}^{n-1}\frac{1}{k!} \end{matrix}\\[1.5ex] \begin{matrix} =O(n!) \cdot \sum\limits_{k=0}^{n-1}\frac{1}{k!} \end{matrix}\\[1.5ex]$

當問題規模(n)?的取值很大時，上式可近似為

$O(n!) \cdot \sum\limits_{k=0}^{n-1}\frac{1}{k!}\\[1.5ex] \approx O(n!) \cdot \sum\limits_{k=0}^{\infty}\frac{1}{k!}\\[1.5ex] \approx O(n!) \cdot e\\[1.5ex] \approx e\cdot O(n!)\\[1.5ex] \approx O(e\cdot n!)\\[1.5ex] \approx O(n!)\\[1.5ex]$

自然對數底e是常數，將其省略后，時間復雜度為 $O(n!)$