【数据结构陈越版笔记】第1章 概述【习题】

本文主要是介绍【数据结构陈越版笔记】第1章 概述【习题】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 碎碎念

我这答案做的可能不对，如果不对，欢迎大家指出错误

2. 答案

1.1 判断正误

（1）$N(\text{log}N{)}^2$是$O(N^2)$的。
（2）$N^2(\text{log}N{)}^2$和$N(\text{log}N{)}^2$具有相同的增长速度。
【答】（1）根据$$O(1)<O\left({\log }_{2}n\right)<O(n)<O\left(n{\log }_{2}n\right)<O\left(n^2\right)<O\left(n^3\right)<O\left(2^n\right)<O(n!)<O\left(n^n\right)$$
故当$n\to \infty$时，$N<N\text{log}N<N^2$，$1<\text{log}N<N$，所以$N<N(\text{log}N{)}^2<N^3$，用不等式法没法求出它到底和$O(N^2)$的关系，于是我们只能通过求二者的数列极限之比来比较大小，由广义的洛必达法则：

广义的洛必达法则：
设$f(x)$和$g(x)$在$\stackrel{o}{U}\left(x_0\right)$上可导（即在$x_0$的去心邻域内可导），若满足：

1. $g^{\prime }(x)\ne 0$；
2. $\underset{x\to x_0}{\lim }g(x)=\infty$，且$\underset{x\to x_0}{\lim }f(x)$存不存在随意；
3. $\underset{x\to x_0}{\lim }\frac{f^{\prime }(x)}{g^{\prime }(x)}$存在；

则有$\underset{x\to x_0}{\lim }\frac{f(x)}{g(x)}=\underset{x\to x_0}{\lim }\frac{f^{\prime }(x)}{g^{\prime }(x)}$

$f(x)=x(\text{log}(x){)}^2$和$g(x)=x^2$是初等函数，在它们的定义域（包括正无穷点是可导的）,由海涅定理，将函数极限归结为数列极限，则$\underset{N\to \infty }{\lim }\frac{N(\text{log}N{)}^2}{N^2}=\underset{N\to \infty }{\lim }\frac{(\text{log}N{)}^2}{N}\stackrel{\text{ 广义洛必达法则，此处以log=ln为例子，其他底的结果是一样的 }}{=}\underset{N\to \infty }{\lim }\frac{\frac{2\text{log}N}{N}}{1}=\underset{N\to \infty }{\lim }\frac{2\text{log}N}{N}=0$，所以当$n\to \infty$时，$N(\text{log}N{)}^2<N^2$，故$N(\text{log}N{)}^2$不是$O(N^2)$的，错误。
（2）由于$\underset{N\to \infty }{\lim }\frac{N^2(\text{log}N{)}^2}{N(\text{log}N{)}^2}=\underset{N\to \infty }{\lim }N=\infty$，所以当$n\to \infty$时，$N^2(\text{log}N{)}^2<N(\text{log}N{)}^2$，$N^2(\text{log}N{)}^2$和$N(\text{log}N{)}^2$不具有相同的增长速度。

1.2 填空题

（1）给定$N\times N$的二维数组$A$，则在不改变数组的前提下，查找最大元素的时间复杂度是（ ）。
【答】查找最大元素的时间复杂度是$O(N^2)$，因为要双层for循环，第一层遍历行，规模为$N$，第二层遍历列，规模为$N$然后去不断比较找到最大元素




（2）斐波那契而数列$F_N$的定义为：$F_0=0,F_1=1,F_N=F_{N-1}+F_{N-2},N=2,3,...$。用递归函数计算$F_N$的空间复杂度是（ ）；时间复杂度是（ ）。
【答】空间复杂度为$O(N)$，时间复杂度为$O\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n\right)$，具体解析过程如下：
补充个前置知识，差分方程：

（1）差分方程：设序列$a_0,a_1,...,a_n,...$简记为 { a n } \{a_{n}\} {an​}，一个把$a_n$与某些个$a_i(i<n)$联系起来的等式称作关于序列 { a n } \{a_{n}\} {an​}的差分方程（又称为递推方程，递归方程）
（2）差分方程的阶：差分方程$f(n)=f(n-1)+f(n-2)+...$中最大下标与最小下标之差称为差分方程的阶。
（3）$k$阶常系数线性差分方程：设差分方程满足：
$$\{\begin{array}{l}H(n)-a_{1}H(n-1)-a_{2}H(n-2)-\cdots -a_{k}H(n-k)=f(n)\\ H(0)=b_0,H(1)=b_1,H(2)=b_2,\cdots ,H(k-1)=b_{k-1}\end{array}$$
其中$a_1,a_2,...,a_k$为常数，$a_k\ne 0$，这个方程称作$k$阶常系数线性差分方程，$b_0,b_1,...b_{k-1}$为$k$个初值，当$f(n)=0$时称这个差分方程为齐次方程；
（4）常系数线性齐次差分方程的特征根：
$$\{\begin{array}{l}H(n)-a_{1}H(n-1)-a_{2}H(n-2)-\cdots -a_{k}H(n-k)=0\\ H(0)=b_0,H(1)=b_1,H(2)=b_2,\cdots ,H(k-1)=b_{k-1}\end{array}$$
方程$x^k-a_1{x}^{k-1}-\cdots -a_k=0$称作该差分方程的特征方程，特征方程的根
（5）一阶常系数线性差分方程：
$$H(n)-aH(n-1)=f(n)$$
其中$a\ne 0$，
当$f(n)\ne 0$，则称此方程为一阶常系数非齐次差分方程；
当$f(n)=0$，则称此方程为一阶常系数齐次差分方程

（5.1）一阶线性齐次差分方程通解的求法（特征根法）：
对于差分方程$H(n)-aH(n-1)=0$，特征方程为$x-a=0$，特征根为$x=a$，故一阶线性齐次差分方程的$H(n)-aH(n-1)=0$的通解为$\bar{H}(n)=C\cdot a^n(C为任意常数)$
（5.2）一阶线性非齐次差分方程通解的求法（齐次通接+非齐次特解）：
H(n)-aH(n-1)=f(n)的通解=齐次方程H(n)-aH(n-1)=0的通解+非齐次的一个特解，其主要有下面两种类型：

（5.2.1）$f(n)=Pt(n)$型
方程$H(n)-aH(n-1)=f(n)$
特解：$H^{\ast }(n)=n^{k}Qt(n)$（$Qt(n)$是与$Pt(n)$通次的待定多项式）
其中$k=\{\begin{array}{l}0,\text{ 若 }1\text{ 不是特征方程的特征根 }\\ 1,\text{ 若 }1\text{ 是特征方程的特征根 }\end{array}$
（5.2.2）$f(n)=A{\beta }^n$型（$A$是某个常数，$\beta \ne 1$）：
方程的特解为：$H^{\ast }(n)=\{\begin{array}{l}p\cdot \beta n,\beta \text{ 不是特征方程的特征根 }\\ p\cdot n^e\cdot {\beta }^n,\beta \text{ 是特征方程的特征根 }e\end{array}\text{, 其中 }p\text{ 为待定常数 }$

（6）二阶常系数线性差分方程：
$$H(n)-aH(n-1)+bH(n-2)=f(n)$$
其中$a$为任意常数，$b\ne 0$，
当$f(n)\ne 0$，则称此方程为二阶常系数非齐次差分方程；
当$f(n)=0$，则称此方程为二阶常系数齐次差分方程
特征方程为$x^2+ax+b=0$
特征根为$x_{1,2}=\frac{-a\pm \sqrt{a^2-4b}}{2}$

（6.1）二阶常系数线性齐次差分方程通解的求法（特征根法）：
通解为$\bar{H}(n)=\{\begin{array}{l}{C}_1{x}_1^n+C_2{x}_2^n\text{ 且 }{C}_1,C_2\text{ 为任意常数, }{x}_1\ne x_2\text{ 且均为实根 }\\ \left(C_1+C_{2}n\right)x^n\text{ 且 }{C}_1,C_2\text{ 为任意常数, }{x}_1=x_2\text{ 且均为实根 }\\ r^n\left(C_1\cos \theta n+C_2\sin \theta n\right)\text{ 且 }r=\sqrt{{\alpha }^2+{\beta }^2}\text{ 又 }\tan \theta =\frac{\beta }{\alpha },x_{1,2}=\alpha \pm \beta i\text{ 且为一对共轭复根 }\end{array}$
（6.2）二阶线性非齐次差分方程通解的求法**（齐次通接+非齐次特解）**：

（6.2.1）$f(n)=Pt(n)$型
特解为$H^{\ast }(n)=n^{k}Qt(n)$,其中$k=\{\begin{array}{l}0,\text{ 若 }1\text{ 不是特征根 }\\ 1,\text{ 若 }1\text{ 是特征单根 }\\ 2,\text{ 若 }1\text{ 是特征重根 }\end{array}$
（6.2.2）$f(n)=A{\beta }^n$型（$A$是某个常数，$\beta \ne 1$）：
特解为$H^{\ast }(n)=\{\begin{array}{l}p\cdot {\beta }^n,\beta \text{ 不是特征根 }\\ p\cdot n^x\cdot {\beta }^n,\beta \text{ 是特征重根 }x\end{array}$
（6.2.3）$f(n)=p(p为常数)$：
当特征根不为1时，将$p$带入原方程求解特解，当特征根为1时，则特解$H^{\ast }(n)=pn$

根据题目，斐波那契数列的递归函数应该写成如下C语言代码：

int fib(int n){if(n==0){return 0;}else if(n==1){return 1;}else{return fib(n-1) + fib(n-2);}
}

题目中要求求的就是递归函数版本，则先分析空间复杂度:
由于函数递归调用的时候必定涉及到函数调用栈，所以得提前说一下，栈是一种线性的先进后出的数据结构，调用函数的时候，其底层是维护了一个函数调用栈，具体怎么做，请看下面的解答：假设问题规模的$n=5$
首先，fib(5)进栈：

fib(4)进栈：

fib(3)进栈：

fib(2)进栈：

fib(2)出栈：

fib(3)出栈：

fib(2)进栈：

fib(2)出栈：

fib(4)出栈：

fib(3)进栈：

fib(2)进栈：

fib(2)出栈：

fib(3)出栈：

fib(5)出栈：

到此，我们来观察一下，我们发现，占用栈内存最多的是这种情况：

输入规模为$N=5$占用了$O(4)$的空间复杂度，经过数学归纳法推理得知，输入规模为$N$时，空间复杂度为$O(N-1)=O(N)$
接下来我们探究一下时间复杂度，其实递归函数完全对应着时间复杂度函数$T(N)$的递推过程，即$T(N)=T(N-1)+T(N-2),T(0)=0,T(1)=1$，亦即$T(N)-T(N-1)-T(N-2)=0$，这个方程恰好是二阶齐次线性差分方程，其特征方程为$x^2-x-1=0$，特征根为$x_1=\frac{1+\sqrt{1+4}}{2}=\frac{1+\sqrt{5}}{2}$，$x_2=\frac{1-\sqrt{1+4}}{2}=\frac{1-\sqrt{5}}{2}$，即有两个不等的特征实根，则方程通解为$\bar{T}(n)=C_1{\left(\frac{1+\sqrt{5}}{2}\right)}^n+C_2{\left(\frac{1-\sqrt{5}}{2}\right)}^n,C_1,C_2\text{ 为任意常数 }$，由于$T(0)=0,T(1)=1$，即
$$\{\begin{array}{l}\bar{T}(0)=C_1+C_2=0\\ \bar{T}(1)=C_1\left(\frac{1+\sqrt{5}}{2}\right)+C_2\left(\frac{1-\sqrt{5}}{2}\right)=1\end{array}$$
求得$C_1=\frac{\sqrt{5}}{5},C_2=-\frac{\sqrt{5}}{5}$
所以原时间复杂度函数为$T(n)=\frac{\sqrt{5}}{5}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right)$，所以时间复杂度为$O\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right)$
当$n\to \infty$时，由于$|\frac{1+\sqrt{5}}{2}|>1,|\frac{1-\sqrt{5}}{2}|<1$，
所以$\underset{n\to \infty }{\lim }{\left(\frac{1+\sqrt{5}}{2}\right)}^n=\infty ,\underset{n\to \infty }{\lim }{\left(\frac{1-\sqrt{5}}{2}\right)}^n=0$
所以，最终的时间复杂度为$O\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n\right)$
这玩意的时间复杂度是指数爆炸级别的，远大于$O(n^k),k>0$

【注】关于$\underset{n\to \infty }{\lim }{\left(\frac{1-\sqrt{5}}{2}\right)}^n=0$的证明，这里引用一下苏德矿高等数学第三版中的证明：

【拓展】这个斐波那契数列还有一个循环的版本，我们来分析一下循环版本的复杂度：

循环版本应该写成如下C语言代码：

int fib(int n){//当n=0时if(n==0){return 0;}//当n=1时if(n==1){return 1;}//当n=2时int fn_1=1; //n-1为1int fn_2=0; //n-2为0int fn_1_2_sum = fn_1 + fn_2; //f(n-1)+f(n-2)为结果//当n>2即n>=3时for(int i = 3; i <= n ; i++){//f(n-1)与f(n-2)都各自往前移动一项fn_2 = fn_1;fn_1 = fn_1_2_sum ;fn_1_2_sum  = fn_1 + fn_2;}return fn_1_2_sum ;
}

全程就用了3个变量，相当于空间复杂度是$O(3)$，也就是常数级的空间复杂度，最终空间复杂度为$O(1)$，一个for循环，循环变量i从3遍历到n，时间复杂度为$O(n-3)=O(n)$

1.3 试分析下面一段代码的时间复杂度：

if(A>B){for(i=0;i<N;i++)for(j=N*N;j>i;j--)A+=B;
}
else{for(i=0;i<N*2;i++)for(j=N*2;j>i;j--)A+=B;
}

【答】如果进入if条件，那么最外层循环最多执行N次，内层循环中，当i=0时，j自减的最多，j从$N^2$开始自减，一直自减到j为1时，就停止自减了，因为j减少到0时，j>i这个条件不满足，无法进入内层循环，则内层循环最多执行$N^2-1$，则if条件下的时间复杂度为$O_{\text{if}}(N(N^2-1))=O_{\text{if}}(N^3-N)=O_{\text{if}}(N^3)$
再看else条件下，外层循环，i从0开始自增到2N-1的时候执行次数最多，即外层循环最多执行$2N-1$次，内层循环，j从$2N$开始自减，当i=0时自减次数最多，自减到1，则内层循环最多执行$2N-1$次，则else条件下的时间复杂度为$O_{\text{else}}((2N-1)(2N-1))=O_{\text{else}}(4N^2-4N+1)=O_{\text{else}}(N^2)$
所以总的时间复杂度为 T ( n ) = max { O if ( N 3 ) , O else ( N 2 ) } = O ( N 3 ) T(n)=\text{max}\{O_{\text{if}}(N^{3}),O_{\text{else}}(N^{2})\}=O(N^{3}) T(n)=max{Oif​(N3),Oelse​(N2)}=O(N3)

1.4 分析例1.2中两个版本的PrintN函数的时间、空间复杂度，并测试它们的实际运行效率。对N=100, 1000, 10000, 100000运行程序，将两版本的N-时间曲线绘在一张图里进行比较分析。

#include <stdio.h>// 循环打印1到N的全部整数
void CirPrintN(int N)
{int i = 0;for(i = 1; i<=N; i++){printf("%d\n", i);}
}
// 递归打印1到N的全部整数
void RecPrintN(int N)
{if(N>0){RecPrintN(N-1);printf("%d\n", N);}
}int main()
{int N = 0;scanf("%d", &N);CirPrintN(N);return 0;
}

【答】第一个循环版本PrintN只有一层for循环，从1打印到N，循环版本PrintN的时间复杂度为$O(N)$，递归版本的PrintN也是打印N次，可以直接看出递归了N次，则递归版本PrintN的时间复杂度为$O(N)$，对于循环版本PrintN，我们看到，只用了一个变量i存储，空间复杂度为$O(1)$，对于递归版本的PrintN，我们能想象到函数调用栈这样一个情况，等到RecPrint(1)入栈后（此时函数调用栈中有RecPrint(N)到RecPrint(2)所有的递归调用过程）才会依次出栈，此时可以看出，空间复杂度为$O(n)$，这个也可以取一个具体的N然后画图说明，类似1.2题（2）。
然后我们用之前提到的【数据结构陈越版笔记】第1章 概论C语言中的计时工具对两种方法进行计时，代码如下：

#include <stdio.h>
#include <time.h>
#include <math.h>clock_t start = 0;     //开始时间
clock_t stop = 0;      //结束时间
double duration = 0.0; //算法一共运行了多长时间#define MAXN 100  // 打印的最大整数N
#define MAXK 1 // 被测函数最大重复调用次数// 循环打印1到N的全部整数
void CirPrintN(int N)
{int i = 0;for (i = 1; i <= N; i++){printf("%d\n", i);}
}
// 递归打印1到N的全部整数
void RecPrintN(int N)
{if (N > 0){RecPrintN(N - 1);printf("%d\n", N);}
}// 此函数用于测试被测函数*f，并且根据case_n输出相应的结果
// case_n是输出的函数编号：1代表函数f1；2代表函数f2
void run(void (*f)(int), int case_n)
{int i = 0;start = clock();//重复调用函数以获得充分多的时钟打点数for (i = 0; i < MAXK; i++) // 调用MAXK次{(*f)(MAXN);}stop = clock();duration = ((double)(stop - start)) / CLK_TCK; // 转换为秒数printf("ticks%d= %f \n", case_n, (double)(stop - start));printf("duration%d = % 6.2e \n", case_n, duration);
}int main()
{run(CirPrintN,1);run(RecPrintN,2);return 0;
}

经过运行代码，得知（每个人机器跑出的结果应该是不太一样的）
当$N=100$时，循环法运行了$2\times 10^{-3}\text{s}$，递归法运行了了$3\times 10^{-3}\text{s}$；
当$N=1000$时，循环法运行了$2.4\times 10^{-2}\text{s}$，递归法运行了了$2.4\times 10^{-2}\text{s}$；
当$N=10000$时，循环法运行了$2.7\times 10^{-1}\text{s}$，递归法出现了函数调用栈溢出错误；
当$N=10000=$时，循环法运行了$2.42\text{s}$，递归法出现了函数调用栈溢出错误；
我们用N从1到3500，步长为1，对两种算法进行N和运行时间的取值，然后结果保存成csv文件（1.csv是循环法的数据，2.csv是递归法的数据，均保存在根目录中），再用Python matplotlib画图（我目前只会用matplotlib画图），取N最大为3500是，再取大一些，会出现函数调用栈溢出情况，这样修改后的C语言代码如下：

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>//N与运行时间的数据写入CSV文件,id为1指代循环法，id为2指代递归法
void WriteToCsv(int id, int N, long double duration)
{FILE* fp = NULL;if (id == 1){fp = fopen("1.csv", "a+"); //在文件末尾继续写入新数据，而不是覆盖}else{fp = fopen("2.csv", "a+"); }if (fp == NULL) {fprintf(stderr, "fopen() failed.\n");exit(EXIT_FAILURE);}fprintf(fp, "%d,%.18Lf\n", N, duration); //保存18位小数，具体情况视机器的情况而定fclose(fp);
}clock_t start = 0;     //开始时间
clock_t stop = 0;      //结束时间
long double duration = 0.0; //算法一共运行了多长时间#define MAXN 3500  // N从1测试到3500，实测我电脑3993开始递归的函数调用栈溢出，为了保险测试到3500
#define MAXK 1 // 被测函数最大重复调用次数// 循环打印1到N的全部整数
void CirPrintN(int N)
{int i = 0;for (i = 1; i <= N; i++){printf("%d\n", i);}
}
// 递归打印1到N的全部整数
void RecPrintN(int N)
{if (N > 0){RecPrintN(N - 1);printf("%d\n", N);}
}// 此函数用于测试被测函数*f，并且根据case_n输出相应的结果
// case_n是输出的函数编号：1代表函数f1；2代表函数f2
void run(void (*f)(int), int case_n)
{//从1到MAXN传参for (int i = 1; i <= MAXN; i++){start = clock();(*f)(i);stop = clock();duration = ((long double)(stop - start)) / CLK_TCK; // 转换为秒数printf("ticks%d= %Lf \n", case_n, (long double)(stop - start));printf("duration%d = % 6.2e \n", case_n, duration);WriteToCsv(case_n, i, duration); //将N和运行时间写入csv文件}
}int main()
{run(CirPrintN, 1);run(RecPrintN, 2);return 0;
}

Python绘图代码如下（需要pandas和matplotlib库）：

import pandas as pd
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'SimHei'  # 设置中文字体# 读取CSV文件
df1 = pd.read_csv('1.csv')
df2 = pd.read_csv('2.csv')# 绘制折线图
plt.figure(figsize=(10, 5))  # 设置图的大小# 绘制1.csv的数据
plt.plot(df1['N'], df1['duration'], color='red', marker='^', label='循环法PrintN折线')  # 红色线条，三角标记# 绘制2.csv的数据
plt.plot(df2['N'], df2['duration'], color='blue', marker='o', label='递归法PrintN折线')  # 蓝色线条，圆圈标记plt.title('PrintN函数N-运行时间折线图')  # 设置图标题
plt.xlabel('N')  # 设置x轴标签
plt.ylabel('运行时间：s')  # 设置y轴标签
plt.grid(True)  # 显示网格
plt.legend()  # 显示图例
plt.show()  # 显示图形

最后将两个算法的N和运行时间绘制折线图到一张图上：

可以看到，时间差不多，毕竟都是O(n)复杂度的算法。

1.5 测试例1.3中秦九韶算法与直接法的效率差别。令$f(x)=1+\sum _{i=1}^{100}{x}^i/i$，计算$f(1.1)$的值。利用clock()函数得到两种算法在同一机器的运行时间。

【答】将之前的代码（详见【数据结构陈越版笔记】第1章 概论）魔改成：

#include <stdio.h>
#include <time.h>
#include <math.h>clock_t start = 0;     //开始时间
clock_t stop = 0;      //结束时间
double duration = 0.0; //算法一共运行了多长时间#define MAXN 10  // 多项式最大项数，即多项式阶数+1
#define MAXK 1e7 // 被测函数最大重复调用次数// n为多项式的项数，a数组存储的是多项式各系数
//普通的循环法求多项式的和
double f1(int n, double a[], double x)
{int i = 0;double p = a[0];for (i = 1; i <= n; i++){p += (a[i] * pow(x, i));}return p;
}//秦九韶法求多项式的和
double f2(int n, double a[], double x)
{int i = 0;double p = a[n];for (i = n; i > 0; i--){p = a[i - 1] + x * p; //从最里面的括号开始算}return p;
}// 此函数用于测试被测函数*f，并且根据case_n输出相应的结果
// case_n是输出的函数编号：1代表函数f1；2代表函数f2
void run(double (*f)(int, double*, double), double a[], int case_n)
{int i = 0;start = clock();//重复调用函数以获得充分多的时钟打点数for (i = 0; i < MAXK; i++) // 调用MAXK次{(*f)(MAXN - 1, a, 1.1);}stop = clock();duration = ((double)(stop - start)) / CLK_TCK; // 转换为秒数printf("ticks%d= %f \n", case_n, (double)(stop - start));printf("duration%d = % 6.2e \n", case_n, duration);
}int main()
{int i = 0;double a[MAXN]; //系数数组for (i = 0; i < MAXN; i++){a[i] = 1.0/(double)i;//系数这儿改动一下}run(f1, a, 1);run(f2, a, 2);return 0;
}

普通循环法求多项式是2.3s，而秦九韶法只需要$2.25\times 10^{-1}\text{s}$

1.6 试分析最大子列和算法1.3的空间复杂度。

【答】最大子列和算法1.3的代码：

// 比较三个数中最大数的宏定义
#define MAX3(A, B, C) (( A > B ? A : B) > C) ? ( A > B ? A : B) : C// 分治法递归求最大子列和
int DivideAndConquer(int* List, int left, int right)
{int MaxLeftSum = INT_MIN; // 左子列的最大和int MaxRightSum = INT_MIN; // 右子列的最大和int MaxLeftBorderSum = INT_MIN; //跨越中点的子列的左侧的和int MaxRightBorderSum = INT_MIN; //跨越中点的子列的右侧的和int LeftBorderSum = 0; //跨越中点的子列的左侧的和（不一定是最大的）int RightBorderSum = 0; //跨越中点的子列的右侧的和int middle = 0; //分治法求分界点的变量s// left与right重合时，递归停止，也就是子列只有一个数字// 这是最小的子列，其和就是这一个元素，如果它的和// 也就是这一个元素为负数或者0，则应该返回0（根据题意）// 如果是LeetCode53，则应该直接返回List[left]，不需要加判断条件// 因为LeetCode53是需要对比负数和的if(left == right){if(List[left] > 0){return List[left];}else{return 0;}}// 求解中点，向右移动一位相当于除2middle = (right + left)>>1;  // 此处也可以等价成(right - left)/2 + left，但是这样写会超时//递归求解左子列和右子列的最大和MaxLeftSum = DivideAndConquer(List, left, middle);MaxRightSum = DivideAndConquer(List, middle + 1, right);//求跨越中点的子列的最大和MaxLeftBorderSum = INT_MIN; //每次求和之前，要将最大值变为无穷小，方便比较LeftBorderSum = 0;//找跨越中点的子列的左侧的最大和（从中点向左遍历）for(int i = middle; i>=left; i--){LeftBorderSum += List[i];if(LeftBorderSum > MaxLeftBorderSum){MaxLeftBorderSum = LeftBorderSum;}}//找跨越中点的子列的右侧的最大和（从中点向右遍历）MaxRightBorderSum = INT_MIN; //每次求和之前，要将最大值变为无穷小，方便比较RightBorderSum = 0;for(int i = middle + 1; i<=right; i++){RightBorderSum += List[i];if(RightBorderSum > MaxRightBorderSum){MaxRightBorderSum = RightBorderSum;}}// 返回左子列，跨越中点的子列和右子列三者中的最大值return MAX3(MaxLeftSum, MaxLeftBorderSum + MaxRightBorderSum, MaxRightSum);
}
int maxSubArray(int* List, int N) {return DivideAndConquer(List, 0, N-1);
}

卡卡！我们还是画图吧，不画图硬推太难了：
假设存在这样一个数组[-1,-2,0]，求其最大子列和，下面画出其函数调用栈的图：
第1步：

第2步：

第3步：

第4步：

第5步：

第6步：

第7步：

第8步：

第9步：

第10步：

第11步：

第12步：

第13步：

第14步：

第15步：

第16步：

第17步：

可以看到，函数调用栈最深的时候有三个递归过程，恰好对应3个元素，所以其空间复杂度应为$O(N)$

1.7 测试最大子列和4种算法的实际运行效率。简单起见，可令List中全部整数位1。当N=2, 4, 6, 8, 10, …, 28, 30时，将各算法的N-时间曲线绘在一张图上，其中时间以毫秒为单位：当N=1000, 2000, …, 10000时，以秒为单位绘出各算法的时间增长曲线。两幅图有什么不同？为什么？

【答】4种算法的代码如下：
时间复杂度为$O(N^3)$的暴力法：

#include <stdio.h>//暴力法
int MaxSubseqSum1(int List[], int N)
{int ThisSum = 0; //当前子列的和int MaxSum = 0; //最大子列和，默认赋值为0，如果和为负数，就只能返回0//i是子列左端位置for (int i = 0; i < N; i++){//j是子列右端位置for (int j = i; j < N; j++){ThisSum = 0;// 把子列和（从List[i]加到List[j]）加一起for (int k = i; k <= j; k++){ThisSum += List[k];}// 如果当前和超过之前的最大和，则最大和赋值成这个if (ThisSum > MaxSum){MaxSum = ThisSum;}}}return MaxSum;
}

时间复杂度为$O(N^2)$的暴力法：

#include <stdio.h>//暴力法2
int MaxSubseqSum2(int List[], int N)
{int ThisSum = 0; //当前子列的和int MaxSum = 0; //最大子列和，默认赋值为0，如果和为负数，就只能返回0//i是子列左端位置for (int i = 0; i < N; i++){ThisSum = 0; // ThisSum清零的工作就放到了j这个循环的外层//j是子列右端位置for (int j = i; j < N; j++){ThisSum += List[j];// 如果当前和超过之前的最大和，则最大和赋值成这个if (ThisSum > MaxSum){MaxSum = ThisSum;}}}return MaxSum;
}

时间复杂度为$O(N\text{log}N)$的分治法：

// 比较三个数中最大数的宏定义
#define MAX3(A, B, C) (( A > B ? A : B) > C) ? ( A > B ? A : B) : C// 分治法递归求最大子列和
int DivideAndConquer(int* List, int left, int right)
{int MaxLeftSum = INT_MIN; // 左子列的最大和int MaxRightSum = INT_MIN; // 右子列的最大和int MaxLeftBorderSum = INT_MIN; //跨越中点的子列的左侧的和int MaxRightBorderSum = INT_MIN; //跨越中点的子列的右侧的和int LeftBorderSum = 0; //跨越中点的子列的左侧的和（不一定是最大的）int RightBorderSum = 0; //跨越中点的子列的右侧的和int middle = 0; //分治法求分界点的变量s// left与right重合时，递归停止，也就是子列只有一个数字// 这是最小的子列，其和就是这一个元素，如果它的和// 也就是这一个元素为负数或者0，则应该返回0（根据题意）// 如果是LeetCode53，则应该直接返回List[left]，不需要加判断条件// 因为LeetCode53是需要对比负数和的if(left == right){if(List[left] > 0){return List[left];}else{return 0;}}// 求解中点，向右移动一位相当于除2middle = (right + left)>>1;  // 此处也可以等价成(right - left)/2 + left，但是这样写会超时//递归求解左子列和右子列的最大和MaxLeftSum = DivideAndConquer(List, left, middle);MaxRightSum = DivideAndConquer(List, middle + 1, right);//求跨越中点的子列的最大和MaxLeftBorderSum = INT_MIN; //每次求和之前，要将最大值变为无穷小，方便比较LeftBorderSum = 0;//找跨越中点的子列的左侧的最大和（从中点向左遍历）for(int i = middle; i>=left; i--){LeftBorderSum += List[i];if(LeftBorderSum > MaxLeftBorderSum){MaxLeftBorderSum = LeftBorderSum;}}//找跨越中点的子列的右侧的最大和（从中点向右遍历）MaxRightBorderSum = INT_MIN; //每次求和之前，要将最大值变为无穷小，方便比较RightBorderSum = 0;for(int i = middle + 1; i<=right; i++){RightBorderSum += List[i];if(RightBorderSum > MaxRightBorderSum){MaxRightBorderSum = RightBorderSum;}}// 返回左子列，跨越中点的子列和右子列三者中的最大值return MAX3(MaxLeftSum, MaxLeftBorderSum + MaxRightBorderSum, MaxRightSum);
}
int maxSubArray(int* List, int N) {return DivideAndConquer(List, 0, N-1);
}

时间复杂度为$O(N)$的在线处理（动态规划）法：

int maxSubArray(int* nums, int numsSize){int result=0;//最开始假定最大值为0，因为这个题目要求的是负数和算为0，如果和LeetCode53一样需要负数和，此处应设置为INT_MINint count =0;//子数组的求和结果for(int i=0;i<numsSize;i++){count = count + nums[i];//count大于假定的最大值，就让假定的最大值等于countif(count > result){result = count;}//加和小于等于0，则其不是最大连续子序列，让count从0开始加//如果加和变成负数，说明从nums[i]开始向前到nums[0]的数无论怎么取连续子数组都只能小于等于result//result记录的是nums[i]之前的数字的最大连续子数组的和//所以，就没必要再回到前面去找加和了，直接从nums[i]向后加和对比//如果从nums[i]开始到最后的加和中出现了加和大于nums[i]之前的最大连续子数组的和result//那就让result赋值为nums[i]后面的最大连续子数组的和的值//这样就找到了最大连续子数组的和if(count<0){count =0;}}return result;
}

魔改一下计时的那个代码如下：

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>//N与运行时间的数据写入CSV文件
//1指的是时间复杂度为O(N^3)的暴力法
//2指的是时间复杂度为O(N^2)的暴力法
//3指的是时间复杂度为O(NlogN)的分治法
//4指的是时间复杂度为O(N)的在线处理（动态规划）法
void WriteToCsv(int id, int N, long double duration)
{FILE* fp = NULL;switch (id){case 1:fp = fopen("1.csv", "a+");break;case 2:fp = fopen("2.csv", "a+");break;case 3:fp = fopen("3.csv", "a+");break;case 4:fp = fopen("4.csv", "a+");break;default:fprintf(stderr, "fopen() failed.\n");exit(EXIT_FAILURE);}if (fp == NULL) {fprintf(stderr, "fopen() failed.\n");exit(EXIT_FAILURE);}fprintf(fp, "%d,%.18Lf\n", N, duration); //保存18位小数，具体情况视机器的情况而定fclose(fp);
}clock_t start = 0;     //开始时间
clock_t stop = 0;      //结束时间
long double duration = 0.0; //算法一共运行了多长时间#define MAXN 30 // 最多测试到长度为30的全为1的数组//时间复杂度为O(N^3)的暴力法
int MaxSubseqSum1(int* List, int N)
{int ThisSum = 0; //当前子列的和int MaxSum = 0; //最大子列和，默认赋值为0，如果和为负数，就只能返回0//i是子列左端位置for (int i = 0; i < N; i++){//j是子列右端位置for (int j = i; j < N; j++){ThisSum = 0;// 把子列和（从List[i]加到List[j]）加一起for (int k = i; k <= j; k++){ThisSum += List[k];}// 如果当前和超过之前的最大和，则最大和赋值成这个if (ThisSum > MaxSum){MaxSum = ThisSum;}}}return MaxSum;
}//时间复杂度为O(N^2)的暴力法
int MaxSubseqSum2(int* List, int N)
{int ThisSum = 0; //当前子列的和int MaxSum = 0; //最大子列和，默认赋值为0，如果和为负数，就只能返回0//i是子列左端位置for (int i = 0; i < N; i++){ThisSum = 0; // ThisSum清零的工作就放到了j这个循环的外层//j是子列右端位置for (int j = i; j < N; j++){ThisSum += List[j];// 如果当前和超过之前的最大和，则最大和赋值成这个if (ThisSum > MaxSum){MaxSum = ThisSum;}}}return MaxSum;
}//时间复杂度为O(NlogN)的分治法
// 比较三个数中最大数的宏定义
#define MAX3(A, B, C) (( A > B ? A : B) > C) ? ( A > B ? A : B) : C// 分治法递归求最大子列和
int DivideAndConquer(int* List, int left, int right)
{int MaxLeftSum = INT_MIN; // 左子列的最大和int MaxRightSum = INT_MIN; // 右子列的最大和int MaxLeftBorderSum = INT_MIN; //跨越中点的子列的左侧的和int MaxRightBorderSum = INT_MIN; //跨越中点的子列的右侧的和int LeftBorderSum = 0; //跨越中点的子列的左侧的和（不一定是最大的）int RightBorderSum = 0; //跨越中点的子列的右侧的和int middle = 0; //分治法求分界点的变量s// left与right重合时，递归停止，也就是子列只有一个数字// 这是最小的子列，其和就是这一个元素，如果它的和// 也就是这一个元素为负数或者0，则应该返回0（根据题意）// 如果是LeetCode53，则应该直接返回List[left]，不需要加判断条件// 因为LeetCode53是需要对比负数和的if (left == right){if (List[left] > 0){return List[left];}else{return 0;}}// 求解中点，向右移动一位相当于除2middle = (right + left) >> 1;  // 此处也可以等价成(right - left)/2 + left，但是这样写会超时//递归求解左子列和右子列的最大和MaxLeftSum = DivideAndConquer(List, left, middle);MaxRightSum = DivideAndConquer(List, middle + 1, right);//求跨越中点的子列的最大和MaxLeftBorderSum = INT_MIN; //每次求和之前，要将最大值变为无穷小，方便比较LeftBorderSum = 0;//找跨越中点的子列的左侧的最大和（从中点向左遍历）for (int i = middle; i >= left; i--){LeftBorderSum += List[i];if (LeftBorderSum > MaxLeftBorderSum){MaxLeftBorderSum = LeftBorderSum;}}//找跨越中点的子列的右侧的最大和（从中点向右遍历）MaxRightBorderSum = INT_MIN; //每次求和之前，要将最大值变为无穷小，方便比较RightBorderSum = 0;for (int i = middle + 1; i <= right; i++){RightBorderSum += List[i];if (RightBorderSum > MaxRightBorderSum){MaxRightBorderSum = RightBorderSum;}}// 返回左子列，跨越中点的子列和右子列三者中的最大值return MAX3(MaxLeftSum, MaxLeftBorderSum + MaxRightBorderSum, MaxRightSum);
}
int MaxSubseqSum3(int* List, int N) {return DivideAndConquer(List, 0, N - 1);
}//时间复杂度为O(N)的在线处理（动态规划）法
int MaxSubseqSum4(int* nums, int numsSize) {int result = 0;//最开始假定最大值为0，因为这个题目要求的是负数和算为0，如果和LeetCode53一样需要负数和，此处应设置为INT_MINint count = 0;//子数组的求和结果for (int i = 0; i < numsSize; i++){count = count + nums[i];//count大于假定的最大值，就让假定的最大值等于countif (count > result){result = count;}//加和小于等于0，则其不是最大连续子序列，让count从0开始加//如果加和变成负数，说明从nums[i]开始向前到nums[0]的数无论怎么取连续子数组都只能小于等于result//result记录的是nums[i]之前的数字的最大连续子数组的和//所以，就没必要再回到前面去找加和了，直接从nums[i]向后加和对比//如果从nums[i]开始到最后的加和中出现了加和大于nums[i]之前的最大连续子数组的和result//那就让result赋值为nums[i]后面的最大连续子数组的和的值//这样就找到了最大连续子数组的和if (count < 0){count = 0;}}return result;
}//创建一个长度为N的全1序列
int* createOnes(int N)
{int* result = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; i++){result[i] = 1;}return result;
}// 此函数用于测试被测函数*f，并且根据case_n输出相应的结果
// case_n是输出的函数编号：
//1指的是时间复杂度为O(N^3)的暴力法
//2指的是时间复杂度为O(N^2)的暴力法
//3指的是时间复杂度为O(NlogN)的分治法
//4指的是时间复杂度为O(N)的在线处理（动态规划）法
void run(int (*f)(int*, int), int case_n)
{//从2到MAXN，取偶数值生成全为1的数组然后计时对比for (int i = 2; i <= MAXN; i=i+2){int* arr = createOnes(i);start = clock();// 运行10^6次，让时间明显一些for (int j = 0; j <= 10e6; j++){(*f)(arr, i);}stop = clock();duration = ((long double)(stop - start)) / CLK_TCK; // 转换为秒数printf("ticks%d= %Lf \n", case_n, (long double)(stop - start));printf("duration%d = % 6.2e \n", case_n, duration);WriteToCsv(case_n, i, duration); //将N和运行时间写入csv文件}
}int main()
{run(MaxSubseqSum1, 1);run(MaxSubseqSum2, 2);run(MaxSubseqSum3, 3);run(MaxSubseqSum4, 4);return 0;
}

最后在根目录生成了100000次运行的时间和N的关系的CSV文件，然后用以下Python脚本画图：

import pandas as pd
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'SimHei'  # 设置中文字体# 读取CSV文件
df1 = pd.read_csv('1.csv')
df2 = pd.read_csv('2.csv')
df3 = pd.read_csv('3.csv')
df4 = pd.read_csv('4.csv')# 还原真实数据，之前是用100000次取得时间，这次除回去，求得平均时间
df1['duration'] = df1['duration'] / 100000
df2['duration'] = df2['duration'] / 100000
df3['duration'] = df3['duration'] / 100000
df4['duration'] = df4['duration'] / 100000# 时间以ms为单位，再乘1000
df1['duration'] = df1['duration'] * 1000
df2['duration'] = df2['duration'] * 1000
df3['duration'] = df3['duration'] * 1000
df4['duration'] = df4['duration'] * 1000# 绘制折线图
plt.figure(figsize=(10, 5))  # 设置图的大小# 绘制1.csv的数据
plt.plot(df1['N'], df1['duration'], color='red', marker='^', label=r'时间复杂度为$O(N^{3})$的暴力法')  # 红色线条，三角标记# 绘制2.csv的数据
plt.plot(df2['N'], df2['duration'], color='blue', marker='o', label=r'时间复杂度为$O(N^{2})$的暴力法')  # 蓝色线条，圆圈标记# 绘制3.csv的数据
plt.plot(df3['N'], df3['duration'], color='green', marker='*', label=r'时间复杂度为$O(N\text{log}N)$的分治法')  # 蓝色线条，圆圈标记# 绘制4.csv的数据
plt.plot(df4['N'], df4['duration'], color='orange', marker='x', label=r'时间复杂度为$O(N)$的在线处理法')  # 蓝色线条，圆圈标记plt.title('N-运行时间折线图')  # 设置图标题
plt.xlabel('N')  # 设置x轴标签
plt.ylabel('运行时间：ms')  # 设置y轴标签
plt.grid(True)  # 显示网格
plt.legend()  # 显示图例
plt.show()  # 显示图形

最后得到N-运行时间曲线图为：

要绘制时间增长曲线图（就是绘制时间复杂度函数的值），就要算一下当前四个算法在处理一个规模的问题需要多少秒，但是这样很难捕捉，题目要求是从1000取到10000，步长为1000这样写，那我们就要求规模为1000的问题处理起来需要多少秒，对于暴力法直接正常求解，对于其他两种方法，需要多次运行，运行100次再除100取平均，因为直接计算会是0s，精度不够，于是将上面的run函数改为：

void run(int (*f)(int*, int), int case_n)
{int* arr = createOnes(1000);start = clock();if (case_n == 1 || case_n == 2){(*f)(arr, 1000);}else{for (int i = 0; i < 100; i++){(*f)(arr, 1000);}}stop = clock();duration = ((long double)(stop - start)) / CLK_TCK; // 转换为秒数printf("ticks%d= %Lf \n", case_n, (long double)(stop - start));printf("duration%d = % 6.2e \n", case_n, duration);WriteToCsv(case_n, 1000, duration); //将N和运行时间写入csv文件
}

最后，暴力法1运行规模1000需要$3.84\times 10^{-1}\text{s}$，暴力法2运行规模1000需要$1\times 10^{-3}\text{s}$，分治法运行规模1000需要$4\times 10^{-5}\text{s}$，在线处理法运行规模1000需要$1\times 10^{-5}\text{s}$，因为每个机器的运行时间不一样，所以我们分别设四种算法的真正的时间复杂度函数为$T_1(N)=a{N}^3,T_2(N)=b{N}^2,T_3(N)=cN\text{log}N,T_4(N)=dN,a,b,c,d均为任意常数$，常数是为了估计真正的时间复杂度函数，$T_1(1000)=a10^9=3.84\times 10^{-1}\text{s},a=3.84\times 10^{-10}$，$T_2(1000)=b10^6=1\times 10^{-3}\text{s},b=1\times 10^{-9}$，$T_3(1000)=c1000{\text{log}}_{2}1000=4\times 10^{-5}\text{s},c=4.012\times 10^{-9}$（底数选2是因为二分法），$T_4(1000)=1000d=1\times 10^{-5}\text{s},d=1\times 10^{-8}$，最终得到的估计的时间复杂度函数为：
$T_1(N)=3.84\times 10^{-10}{N}^3\text{s}$
$T_2(N)=1\times 10^{-9}{N}^2\text{s}$
$T_3(N)=4.012\times 10^{-9}N{\text{log}}_{2}N\text{s}$
$T_4(N)=1\times 10^{-8}N\text{s}$
最后使用如下Python脚本画出时间增长曲线：

import matplotlib.pyplot as plt
import numpy as npplt.rcParams['font.family'] = 'SimHei'  # 设置中文字体# log函数
def log(base, x):return np.log(x) / np.log(base)x = np.linspace(1000, 10000, 10)  # 生成1000到10000之间的10个数据点作为x轴
y1 = 3.84e-10 * x * x * x  # 暴力法1时间复杂度函数
y2 = 1e-9 * x * x  # 暴力法2时间复杂度函数
y3 = 4.012e-9 * x * log(2, x)  # 分治法时间复杂度函数
y4 = 1e-8 * x  # 在线处理法时间复杂度# 创建一个Matplotlib图表
plt.figure(figsize=(10, 6))  # 设置图表的大小# 绘制折线图
plt.plot(x, y1, label=r'$T_{1}(N)=3.84\times10^{-10}N^{3}\text{s}$', color='blue', linewidth=2)
plt.plot(x, y2, label=r'$T_{2}(N)=1\times10^{-9}N^{2}\text{s}$', color='red', linewidth=2)
plt.plot(x, y3, label=r'$T_{3}(N)=4.012\times10^{-9}N\text{log}_{2}N\text{s}$', color='green', linewidth=2)
plt.plot(x, y4, label=r'$T_{4}(N)=1\times10^{-8}N\text{s}$', color='orange', linewidth=2)# 添加标题和标签
plt.title('时间增长曲线')
plt.xlabel('N')
plt.ylabel('时间：s')# 添加图例
plt.legend()# 自定义坐标轴范围
plt.xlim(1000, 10000)
plt.ylim(0, 400)# 添加网格线
plt.grid(True, linestyle='--', alpha=0.6)# 显示图像
plt.show()

两幅图增长趋势是一样的，只不过一个N-运行时间曲线是实际运行时间，另一个时间增长曲线是理论估计时间，时间增长曲线能描述当N充分大的时候的趋势。

1.8 查找算法中的“二分法”是这样定义的：给定N个从小到大排好序的整数序列List[]，以及某待查找整数X，我们的目标是找到X在List中的下标，即若有List[i]=X，则返回i；否则返回-1表示没有找到。二分法是先找到序列的中点List[M]，与X进行比较，若下个等则返回中点下标；否则，若List[M]>X，则在左边的子系列中查找X；若List[M]<X，则在右边的子系列中查找X。试写出算法的伪码描述，并分析最坏，最好情况下的时间、空间复杂度。

【答】二分查找，可以用循环实现也可以用递归实现，这里我给出我的文章【代码随想录刷题记录】LeetCode704二分查找
中左闭右闭情况的代码进行分析（循环实现，改成了C语言版本重新实现了一下）：

int search(int* nums, int numsSize, int target){int low = 0;//low指针int high = numsSize-1;//high指针int mid = 0;//折半点while(low<=high){mid = (low+high)>>1;//右移1位相当于除2if(nums[mid]==target){return mid;}else if(target < nums[mid])//小于在左半侧查找{high = mid-1;}else{low = mid+1;//大于在右半侧查找}}//没找到返回-1return -1;
}

先分析最坏时间复杂度，当要找的值在最左侧或者最右侧的时候，运行时间最多，假设要找的值在最右侧，low要不断地移动直到大于high，设数组长度为M，while循环的代码执行了n次，$low(n)$表示第n次low的取值，则$high=M，low(n)=mid+1=\frac{low(n-1)+high}{2}+1=\frac{low(n-1)+M+2}{2}$即$low(n)-\frac{1}{2}low(n-1)=\frac{M+2}{2},low(1)=0,low(2)=\frac{low(1)+M+2}{2}=\frac{M+2}{2}$，这是一个一阶线性非齐次差分方程，
其特征方程为$x-\frac{1}{2}=0$
即特征根为$x=\frac{1}{2}$
故齐次通解为$\overline{low}(n)=C{\left(\frac{1}{2}\right)}^n,C为任意常数$
则特解为$lo{w}^{\ast }(n)=n^{0}p=p,p为任意常数$
则$p-\frac{1}{2}p=\frac{M+2}{2}$，所以$p=M+2$
所以非齐次通解为$low(n)=C{\left(\frac{1}{2}\right)}^n+M+2,C为任意常数$
又因为$low(1)=\frac{1}{2}C+M+2=0$，所以$C=-\frac{M+2}{2}$
所以$low(n)=-\frac{M+2}{2}{\left(\frac{1}{2}\right)}^n+M+2$
当要找的值在最右侧时，$low(n)=M$，所以有：
$M=-\frac{M+2}{2}{\left(\frac{1}{2}\right)}^n+M+2$解得$n={\text{log}}_2\frac{M+2}{4}$
M其实就是问题规模N，n是时间复杂度函数$T(n)$，则其最坏时间复杂度为$O({\text{log}}_2\frac{N+2}{4})=O(\text{log}N)$
最好时间复杂度就是中点对应就是要找的元素，一下子就找到了，所以最好时间复杂度为$O(1)$
我们在此算法中就用到了三个变量low,high,mid,所以空间复杂度无论好坏都是常数级的$O(1)$

1.9 给定存储了N个从小到大排好序的整数数组List[]，试给出算法将任一给定整数X插入数组中合适的位置，以保持结果依然有序。分析算法在最坏、最好情况下的时间、空间复杂度。

【答】

#include <stdio.h>
#include <stdlib.h>//arr是指向待插入数组的指针，n是待插入的数组的长度，m是待插入的值
//返回的是插入后的新数组的长度
//C语言函数参数默认值传递，没有引用，因此只能传入指向旧数组的指针（即指向指针的指针）
int InsertArray(int** arr, int n, int m)
{int* old = *arr; //旧的数组指针int* temp = (int*)malloc((sizeof(int)) * (n + 1)); // 开辟比原来数组长度多1的内存空间当作新的数组//判断开辟的空间是否成功if (temp == NULL){printf("内存不足！\n");return -1;}//将原来数组的元素拷贝到新数组for (int i = 0; i < n; i++){temp[i] = old[i];}int k = n; //记录应该插入的位置下标，数组中若没有元素，默认从n=0开始插入，若遍历到最后都没有大于等于m的元素，则正好在最后位置插入//因为数组有序，只需要找到首个大于等于m的元素，记录此时的下标for (int i = 0; i < n; i++){if (old[i] >= m){k = i;break; // 找到后就跳出循环}}//将k所指元素及其后面的元素都向后移动一个空间（在新的temp数组中）for (int i = n; i > k; i--){temp[i] = temp[i - 1];}temp[k] = m; //插入元素位置free(old); //释放旧数组*arr = temp; //arr指针指向新数组return n + 1;
}int main()
{int* a = (int*)malloc(sizeof(int) * 3); //开辟长度为3的动态数组if (a == NULL){printf("内存不足！\n");return 0;}a[0] = 1;a[1] = 2;a[2] = 3;int **arr = &a; //指向动态数组的指针，便于直接修改值int N = InsertArray(arr, 3, 2);//打印数组结果for (int i = 0; i < N; i++){printf("%d\n", a[i]);}return 0;
}

运行结果：

分析时间复杂度，函数中常数级别的复杂度不需要看，在无穷趋向下都被略掉了，现在看循环中的时间复杂度，首先将原来数组的元素拷贝到新数组的循环是$O(N)$，找到要插入的下标，有可能要插入的值比数组中的元素都大，此时遍历了整个数组，时间复杂度为$O(n)$，将下标k对应的后面的元素全部向后移动1个位置，假设要插入的值比数组中的元素都小，整个数组后移1位，时间复杂度为$O(n)$，最后，总的时间复杂度为$O(N+N+N)=O(N)$，对于空间复杂度，抛出常数级别的变量，我们创建了一个新的长度为$N+1$的数组，则空间复杂度为$O(N+1)=O(N)$

1.10 试给出判断N是否为质数的$O(\sqrt{N})$的算法。

【答】素数一般指质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。根据定义，可以从2~n-1依次试除，判断n是否有约数（约数,又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数,就说a能被b整除,或b能整除a。a称为b的倍数,b称为a的约数。记作$b|a$），若有则n不是质数，假设 $d$ 可以整除$n$($\frac{n}{d}$是整数，$d|n$)，那么它们的商 $\frac{n}{d}$ 也能整除$n$（$\frac{n}{\frac{n}{d}}=d$，$\frac{n}{d}|n$），若约数是成对（5×7=35，5×5=25）出现的，必定是一大一小或者相等，则假设$d\le \frac{n}{d}$，即$d^2\le n$，亦即$d\le \sqrt{n}$（因为$d$是自然数，必然大于0，所以不会出现开根号取负的结果），所以每次判断只需要判断到 $\sqrt{n}$ 即可。

实际上，这个引理来自初等数论，引用一下陈景润版初等数论第一册第五页引理6：
【前置知识】




【注】书中给的证明看得不是太明白，尤其是c大于等于0那里，如果评论区有高人请告诉我为什么能推出$c\ge 0$（我感觉像是说因为c>0，所以c大于等于0），我只推出>0，我自己证了一下，此处用的反证法，因为$|a|||b|$，所以有一个整数$c$，使得$|a|=|b|c$，如果$|a|=0$，则有$a=0$，假设$|a|>0$，则由于$|a|<|b|$有$0<|a|<|b|$，又由于$|a|=|b|c>0,|b|>0$则$c>0$，且$c=\frac{|a|}{|b|}$，又因为$|b|>|a|>0$，所以$c=\frac{|a|}{|b|}<1$，所以$0<c<1$这与$c$是一个整数矛盾，故如果$a,b$都是整数，而$|a|<|b|,|b|||a|$，则有$a=0$.



【注】一个数的因数都小于等于其本身，且在证明的反证法部分，假设$b$是复合数，$b$一定有大于1而不等于$b$的因数$c$，所以$1<c<b$，后来又证明$c$是$a$的因数，结果此处$c$比$b$小了，和前面$b$是$a$的大于1最小因数矛盾了（因为此时$c$是最小因数了），故得证。
【引理6】这个引理6是解决本题的关键。

【注】由于$a$被大于1而小于$\sqrt{a}$的整数都除不尽，且$a=bc$，$b$和$c$是整数且都为$a$的因数，所以$b>\sqrt{a},c>\sqrt{a}$

由引理6可知，因为$a$是整数，$a$要是复合数，则一定有大于1即大于等于2而小于根号a的因数，所以只要从2遍历到根号a，发现能整除，就是复合数，如果过了一遍循环遍历，没有能整除的数，就是素数，这样一看此种算法遍历到最后，最多是$O(\sqrt{n})$的时间复杂度，但是我们要注意，此处判断条件不能直接写i<sqrt(a)，因为sqrt函数在C语言的math.h头文件定义，其用牛顿迭代法求解根号，时间复杂度更复杂，我们应该换一下等价形式，循环变量$i\le \sqrt{a}$等价于$i^2<a$，乘法指令要比开根号迭代运行得快，思路明确后，代码如下：

#include <stdio.h>
#include <stdlib.h>//时间复杂度为$O(\sqrt{n})$的判断素数的算法
//0代表不是素数，1代表是素数
int isPrime(int a)
{//素数的前提是自然数，不是自然数不行if (a <= 0){return 0;}for (int i = 2; i * i <= a; i++){//这期间有一个能整除的，最后结果都是复合数if (a % i == 0){return 0;}}//最后都没整除，则是素数return 1;
}//输出是否是素数的结果
void printIsPrime(int a)
{if (isPrime(a)){printf("%d", a);printf("是素数\n");}else{printf("%d", a);printf("不是素数\n");}
}int main()
{printIsPrime(-1);printIsPrime(0);printIsPrime(4);printIsPrime(5);printIsPrime(10);printIsPrime(23);printIsPrime(1523);printIsPrime(1524);return 0;
}

运行结果：

时间复杂度为$O(\sqrt{N})$

1.11 试给出计算$x^N$的时间复杂度为$O({\text{log}}_N)$的算法。

【答】此题目对应LeetCode50 Pow(x,n)，此处是计算整数次幂
为了能写出低于$O(n)$时间复杂度的算法，肯定要让计算机记住中间的一些计算结果，比如$x^8$，最开始是从$x$，$x^2$开始计算，如果我们知道了$x^2$就相当于知道了$x^4=x^2{x}^2$，知道了$x^4$相当于知道了$x^8=x^4{x}^4$，于是我们知道，如果我们最开始通过不断地计算Pow(x,n/2)，即乘$x^{\frac{n}{2}}$一直递归到幂数为0，然后我们再将每次递归得到的$x^{\frac{n}{2}}$相乘即$x^{\frac{n}{2}}{x}^{\frac{n}{2}}=x^n$记作上一次递归的计算结果，这是偶数次幂的情况，奇数次幂的情况是，假如计算$x^9$，最开始是从$x$，$x^2$开始计算，如果我们知道了$x^2$就相当于知道了$x^4=x^2{x}^2$，知道了$x^4$相当于知道了$x^8=x^4{x}^4$，此时还差乘一个$x$，那需要判断幂数是偶数就正常二分，是奇数就乘个$x$再二分即可，但是我们目前只考虑了幂为自然数的情况，如果为0则返回1，如果为负数，应该按正数（取个负）计算，然后返回其倒数，所以我们只需要先考虑幂为自然数的情况，再根据幂的正负号决定返回倒数还是本身：
递归法：

double quickMul(double x, long long n)
{//为0返回其本身if(n == 0){return 1.0;}double y = quickMul(x, n/2); //求x^(n/2)的情况递归，一直递归到n为0为止//分奇数还是偶数，奇数需要多乘个xif(n % 2 == 0){//偶数直接返回两个二分的结果相乘return y * y;}else{//奇数需要乘个xreturn y * y * x;}
}
double myPow(double x, int n) {//大于0按幂为自然数情况考虑if(n > 0){return quickMul(x, n);}//小于0取倒数（0的情况已经考虑到，直接返回1）else{return 1.0 / quickMul(x,-n);}
}

证明时间复杂度过程：递归法的时间复杂度函数为$T(n)$，则它是不断二分，根据double y = quickMul(x, n/2);的递归调用，然后每一次都有一个常数时间复杂度的判断奇偶的过程，则有$T(n)=T(\frac{n}{2})+O(1)=T(\frac{n}{4})+O(1)+O(1)=...=T(\frac{n}{2^k})+kO(1)$
递归到最后，问题规模为1，即$\frac{n}{2^k}=1$，所以$k={\text{log}}_{2}n$，于是
$T(n)=T(1)+O(1){\text{log}}_{2}n=T(1)+O({\text{log}}_{2}n)$，所以时间复杂度为$O({\text{log}}_{2}n)$
循环法：递归需要额外的函数调用栈的空间，我们尝试改成循环求解：
我们知道任何数都能用二进制表示为$b=k_{i-1}{2}^{i-1}+k_{i-2}{2}^{i-2}+...+k_0{2}^0$
即每个整数都可以唯一表示为若干指数不重复的2的次幂和，则$a^b=a^{k_{i-1}{2}^{i-1}}\times a^{k_{i-2}{2}^{i-2}}\times ...\times a^{k_0{2}^0}$
且$a^{2i}=(a^{2i-1}{)}^2$，以LeetCode官方举的例子为例，求$x^{77}$，按照分治的方法，先求$x^{\lfloor \frac{n}{2}\rfloor }$，即求$x^{\lfloor \frac{77}{2}\rfloor }=x^{38}$，然后求$x^{\lfloor \frac{38}{2}\rfloor }=x^{19}$，然后是$x^{\lfloor \frac{19}{2}\rfloor }=x^9$……以此类推，最后得到要计算的顺序：
$$x\to x^2\to x^4\to x^9\to x^{19}\to x^{38}\to x^{77}$$
然后从左向右计算，根据幂的奇偶性判断是否需要乘$x$
我们将额外乘$x$的部分打一个加号：
$$x\to x^2\to x^4{\to }^{+}{x}^9{\to }^{+}{x}^{19}\to x^{38}{\to }^{+}{x}^{77}$$
$\{\begin{array}{l}{x}^{38}{\to }^{+}{x}^{77}\text{ 中额外乘的 }x\text{ 在 }{x}^{77}\text{ 中贡献了 }x\text{因此在}{x}^{77}\text{中贡献了}{x}^{2^0}\text{ ； }\\ x^9{\to }^{+}{x}^{19}\text{ 中额外乘的 }x\text{ 在之后被平方了 }2\text{ 次}，\text{即}(x^2{)}^2=x^4\text{，因此在 }{x}^{77}\text{ 中贡献了 }{x}^{2^2}=x^4\text{ ； }\\ x^4{\to }^{+}{x}^9\text{ 中额外乘的 }x\text{ 在之后被平方了 }3\text{ 次，即 }{\left({\left(x^2\right)}^2\right)}^2={\left(x^4\right)}^2=x^8\text{ ，因此在 }{x}^{77}\text{ 中贡献了 }{x}^{2^3}=x^8\text{ ； }\\ \text{ 最初的 }x\text{ 在之后被平方了 }6\text{ 次，因此在 }{x}^{77}\text{ 中 }\text{ 贡献了 }{x}^{2^6}=x^{64}\text{ 。 }\end{array}$
77的二进制表示为1001101B，二进制表示中的1的位置从右到左（从下标0开始）恰好和贡献的$x$的幂数对应的$2$的次方数相同，因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，代码如下：

double quickMul(double x, long long n) 
{// 只考虑自然数的情况double result = 1.0; // 初始为1，幂数为0时，它为1// 贡献的初始值为xdouble x_con = x;// 对N进行二进制拆分并计算答案while (n > 0) {//如果当前数的最低位是1，则需要乘贡献的xif(n % 2 == 1){result *= x_con;}// 将贡献不断地平方x_con *= x_con;// 每次除2，相当于找到新的最低位，除2相当于右移1位// 比如1011B除2，就变成了101，右移动1位// 这样每次都能通过除2取余判断新的最低位，直到右移不了位置// 我们是按次幂数的二进制求解n = n >> 1;}return result;
}
double myPow(double x, int n) 
{//大于0按幂为自然数情况考虑if(n > 0){return quickMul(x, n);}//小于0取倒数（0的情况已经考虑到，直接返回1）else{return 1.0 / quickMul(x, -n);}
}

分析时间复杂度：假设问题规模$n$，则$T(n)$时，$n$通过不断除2接近变成规模位1，那么就是$T(n)=T(\frac{n}{2})$，和上面的递推方程一致，所以时间复杂度为$O(\text{log}N)$

3. 总结

想读明白陈姥姥的书，确实需要懂一些离散数学的知识，我也准备重新回顾看一看，顺带再看看数论。

这篇关于【数据结构陈越版笔记】第1章 概述【习题】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---