table {
border-collapse: collapse;
width: 100%;
margin-bottom: 1rem;
}
th, td {
border: 1px solid #ddd;
padding: 8px;
text-align: left;
}
th {
background-color: #f2f2f2;
}
tr:nth-child(even) {
background-color: #f9f9f9;
}
pre {
background-color: #f8f8f8;
padding: 15px;
border-radius: 4px;
overflow-x: auto;
}
27、我们可以通过基于数组预排序的两部分算法来检查数组的所有元素是否不同。a. 如果预排序由时间效率为Ω(n log n)的算法完成，那么整个算法的时间效率类别是什么？b. 如果用于预排序的排序算法需要一个大小为n的额外数组，那么整个算法的空间效率类别是什么？
a. 整个算法的时间效率类别为Ω(n log n)。b. 整个算法的空间效率类别为Θ(n)。
28、有限非空实数集R的范围定义为R中最大元素和最小元素的差值。对于下面给出的R的每种表示方式，用英语描述一个计算范围的算法。使用最合适的符号（O、Ω或Θ）指出这些算法的时间效率类别。a. 有重复元素的未排序数组；b. 有重复元素的已排序数组；c. 未排序的单链表；d. 高度平衡树。
a. 算法：遍历未排序数组，找到最大值和最小值，然后计算它们的差值。
时间效率类别：Θ(n)。
b. 算法：由于数组已排序，最大值是数组最后一个元素，最小值是数组第一个元素，直接计算它们的差值。
时间效率类别：Θ(1)。
c. 算法：遍历未排序的单链表，找到最大值和最小值，然后计算它们的差值。
时间效率类别：Θ(n)。
d. 算法：在高度平衡树中，最小值在最左节点，最大值在最右节点，找到这两个节点并计算差值。
时间效率类别：Θ(log n)。
29、考虑以下算法。算法 Foo(n) //输入：一个非负整数 n ，Sum ← 0 ，对于 i 从 1 到 n 执行：Sum ← Sum + i/i! ，返回 Sum 。a. 这个算法计算什么？b. 它的基本操作是什么？c. 基本操作执行了多少次？d. 这个算法的效率类别是什么？e. 提出一个改进方案或更好的算法，并指出其效率类别。如果做不到，尝试证明实际上无法做到。
a. 该算法计算从 1 到 n 的 i/i! 的和。
b. 基本操作是加法和除法运算（即 i/i! 的计算和 Sum + i/i! 的计算）。
c. 基本操作执行了 n 次。
d. 效率类别为 Θ(n)。
e. 目前基于循环的计算方式较直接，难以有本质上更好的算法。因为该计算需要遍历从 1 到 n 的每个数进行计算，时间复杂度至少为 Θ(n) ，所以当前算法已是最优效率类别。
30、用数学归纳法或遵循10岁学童卡尔·弗里德里希·高斯（1777 – 1855，后来成为最伟大的数学家之一）的思路，证明公式$sum_{i = 1}^{n}i=1 + 2+cdots + n=frac{n(n + 1)}{2}$。
方法一：数学归纳法
基础步骤
：当 $ n = 1 $ 时，等式左边 $ sum_{i = 1}^{1}i=1 $，等式右边 $ frac{1 imes(1 + 1)}{2}=frac{1 imes2}{2}=1 $。左边等于右边，所以当 $ n = 1 $ 时，公式成立。
归纳假设
：假设当 $ n = k $（$ k $ 为正整数）时，公式 $ sum_{i = 1}^{k}i=frac{k(k + 1)}{2} $ 成立。
归纳步骤
：当 $ n=k + 1 $ 时，
∑i=1k+1i=∑i=1ki+(k+1)∑i=1k+1i=∑i=1ki+(k+1)
由归纳假设可知 $ sum_{i = 1}^{k}i=frac{k(k + 1)}{2} $，则
∑i=1k+1i=k(k+1)2+(k+1)=(k+1)(k2+1)=(k+1)(k+2)2=(k+1)[(k+1)+1]2∑i=1k+1i=k(k+1)2+(k+1)=(k+1)(k2+1)=(k+1)(k+2)2=(k+1)[(k+1)+1]2
这表明当 $ n = k + 1 $ 时，公式也成立。由数学归纳法原理，对于任意正整数 $ n $，公式
∑i=1ni=n(n+1)2∑i=1ni=n(n+1)2
都成立。
方法二：高斯的思路
设
S=1+2+⋯+(n−1)+nS=1+2+⋯+(n−1)+n
将其倒序写为
S=n+(n−1)+⋯+2+1S=n+(n−1)+⋯+2+1
将这两个式子对应项相加，可得
2S=(1+n)+(2+(n−1))+⋯+((n−1)+2)+(n+1)2S=(1+n)+(2+(n−1))+⋯+((n−1)+2)+(n+1)
可以发现每一项的和都为 $ n + 1 $，一共有 $ n $ 项。所以
2S=n(n+1)2S=n(n+1)
两边同时除以 $ 2 $，得到
S=n(n+1)2S=n(n+1)2
即
∑i=1ni=n(n+1)2∑i=1ni=n(n+1)2
31、考虑以下算法。算法GE(A[0..n – 1, 0..n]) //输入：一个n × (n + 1)的实数矩阵A[0..n – 1, 0..n] 对于i从0到n – 2 对于j从i + 1到n – 1 对于k从i到n A[j, k] ← A[j, k] – A[i, k] * A[j, i] / A[i, i] a. 找出该算法的时间效率类别。b. 这段伪代码存在什么明显的低效之处，如何消除它以加快算法速度？
a. 该算法有三层嵌套循环，外层循环执行 $ n – 1 $ 次，中层循环执行次数随 $ i $ 变化，内层循环执行 $ n – i + 1 $ 次，总的执行次数大致为 $ O(n^3) $。
b. 明显的低效之处在于每次内层循环都要计算 $ frac{A[j, i]}{A[i, i]} $，可以将其提前计算并存储，避免重复计算，从而加快算法速度。
32、爬楼梯问题：如果每步可以爬一阶或两阶楼梯，求爬n阶楼梯有多少种不同的方法。例如，爬3阶楼梯有三种方法：1 – 1 – 1、1 – 2和2 – 1。
动态规划问题解析
这是一个经典的动态规划问题，设 $ f(n) $ 表示爬 $ n $ 阶楼梯的不同方法数。
1. 确定边界条件：
当 $ n = 1 $ 时，只有一种方法，即一次爬一阶，所以 $ f(1) = 1 $。
当 $ n = 2 $ 时，有两种方法：1 – 1 或 2，所以 $ f(2) = 2 $。
2. 推导状态转移方程：
对于 $ n > 2 $ 的情况，最后一步要么是从 $ n – 1 $ 阶爬一阶到达 $ n $ 阶，要么是从 $ n – 2 $ 阶爬两阶到达 $ n $ 阶。所以：
f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2)
这其实就是斐波那契数列的递推公式。
3. 计算 $ f(n) $：
可以使用循环的方式从边界条件开始逐步计算到 $ f(n) $。
Python代码示例：
def climb_stairs(n):
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2
for i in range(3, n + 1):
c = a + b
a = b
b = c
return b
该算法的时间复杂度为 $ O(n) $，空间复杂度为 $ O(1) $。
33、根据以下算法基本操作计数的经验观察，推测该算法可能的效率类别：规模1000、2000、3000、4000、5000、6000、7000、8000、9000、10000对应的计数分别为11966、24303、39992、53010、67272、78692、91274、113063、129799、140538。
从给出的数据看，随着输入规模线性增长，基本操作计数的增长并非严格线性，更接近二次增长趋势，所以该算法可能的效率类别为
O(n²)
。
34、经过尺度变换，是否可以使凸散点图看起来像线性图？如果可以，怎么做？
可以。对于指数算法的凸散点图，使用对数尺度处理纵轴，即将纵轴绘制 $log_a M(n)$ 而非 $M(n)$（常用对数底数为 2 或 10），此时真正的指数算法散点图在该坐标系中会近似线性函数。
35、什么是蛮力算法？请举例说明。
蛮力算法简介
蛮力算法是一种直接解决问题的方法，通常基于问题陈述和相关概念的定义。
例如
：
对于求非零数
a
的非负整数
n
次幂的问题，根据幂运算的定义，
aⁿ
等于
n
个
a
相乘，因此可以通过将 1 乘以
a
共
n
次来计算
aⁿ
，这就是一个蛮力算法的例子。
36、蛮力算法能否用于解决幂运算问题？请举例说明。
可以。以计算非零数 $ a $ 的非负整数 $ n $ 次幂为例，根据幂运算定义，$ a^n $ 等于 $ n $ 个 $ a $ 相乘，可通过将 1 与 $ a $ 相乘 $ n $ 次来计算 $ a^n $，这是典型的蛮力算法应用。
37、与其他高效算法相比，蛮力算法有哪些优点？
与其他一些策略不同，蛮力法适用于非常广泛的问题，似乎是唯一难以指出其不能解决的问题的通用方法。
对于一些重要问题，如排序、搜索、矩阵乘法、字符串匹配，蛮力法能产生至少具有一定实用价值且对实例规模无限制的合理算法。
如果一个问题只需解决少量实例，且蛮力算法能以可接受的速度解决这些实例，那么设计更高效算法的成本可能是不合理的。
即使总体上效率太低，蛮力算法仍可用于解决小规模问题实例。
蛮力算法可作为衡量解决问题的更高效替代算法的标准，具有重要的理论或教育目的。
38、使用选择排序将列表 S, O, R, T, I, N, G 按字母顺序排序。
第一步：在整个列表中找到最小元素 G，与第一个元素 S 交换，得到 G, O, R, T, I, N, S；
第二步：在剩余元素 O, R, T, I, N, S 中找到最小元素 I，与第二个元素 O 交换，得到 G, I, R, T, O, N, S；
第三步：在剩余元素 R, T, O, N, S 中找到最小元素 N，与第三个元素 R 交换，得到 G, I, N, T, O, R, S；
第四步：在剩余元素 T, O, R, S 中找到最小元素 O，与第四个元素 T 交换，得到 G, I, N, O, T, R, S；
第五步：在剩余元素 T, R, S 中找到最小元素 R，与第五个元素 T 交换，得到 G, I, N, O, R, T, S；
第六步：在剩余元素 T, S 中找到最小元素 S，与第六个元素 T 交换，得到 G, I, N, O, R, S, T。
最终排序结果为 G, I, N, O, R, S, T。
39、请判断排序算法是否稳定并说明理由
虽然大多数基本排序算法是稳定的，但不能匆忙给出答案。
40、顺序搜索（无哨兵，在其输入的标准假设下）进行的平均键比较次数由公式Cavg(n) = p(n + 1)/2 + n(1 – p)给出，其中p是成功搜索的概率。对于固定的n，确定该公式产生Cavg(n)最大值和最小值时p的值（0 ≤ p ≤ 1）。
对公式 $ C_{ ext{avg}}(n) = frac{p(n + 1)}{2} + n(1 – p) $ 进行化简：
Cavg(n)=p(n+1)2+n−np =p(n+1−2n)2+n =p(1−n)2+nCavg(n)=p(n+1)2+n−np =p(n+1−2n)2+n =p(1−n)2+n
因为 $ n $ 为固定值：
当 $ n > 1 $ 时，$ 1 – n < 0 $，$ C_{ ext{avg}}(n) $ 是关于 $ p $ 的减函数，所以：
当 $ p = 0 $ 时，$ C_{ ext{avg}}(n) $ 取得最大值 $ n $；
当 $ p = 1 $ 时，$ C_{ ext{avg}}(n) $ 取得最小值 $ frac{n + 1}{2} $。
当 $ n = 1 $ 时，$ C_{ ext{avg}}(n) = n $，此时最大值和最小值都为 1，$ p $ 可取 $[0, 1]$ 内任意值。
当 $ n < 1 $ 时（$ n $ 为元素个数，通常为正整数，这里仅从数学角度分析），$ 1 – n > 0 $，$ C_{ ext{avg}}(n) $ 是关于 $ p $ 的增函数，所以：
当 $ p = 1 $ 时，$ C_{ ext{avg}}(n) $ 取得最大值 $ frac{n + 1}{2} $；
当 $ p = 0 $ 时，$ C_{ ext{avg}}(n) $ 取得最小值 $ n $。
41、在解决字符串匹配问题时，从右向左比较模式和文本字符而不是从左向右比较有什么优势吗？
有优势。从右向左比较的思想能产生更简单的算法，如Boyer – Moore算法从右向左比较字符，其衍生的简化版Horspool算法也较为简单，且在随机字符串上，Horspool算法不一定比Boyer – Moore算法效率低。
42、你认为如何提高顺序搜索的效率？
提高顺序搜索效率的方法有两种：
一是在实现顺序搜索时，将搜索键附加到列表末尾，可消除列表末尾检查；
二是若给定列表已排序，搜索时一旦遇到大于或等于搜索键的元素，即可停止搜索。
43、设x1 < x2 <… < xn是代表沿着一条直路分布的n个村庄坐标的实数。需要在这些村庄中的一个建造一个邮局。设计一个高效算法，找出使村庄与邮局之间平均距离最小的邮局位置。
当 $ n $ 为奇数时，选择位于中间位置（即第 $ frac{n + 1}{2} $ 个）的村庄建邮局；
当 $ n $ 为偶数时，选择第 $ frac{n}{2} $ 个或第 $ left( frac{n}{2} + 1
ight) $ 个村庄建邮局，可使平均距离最小。
44、设x1 < x2 <… < xn是代表沿着一条直路分布的n个村庄坐标的实数。需要在这些村庄中的一个建造一个邮局。设计一个高效算法来找到使村庄到邮局的最大距离最小的邮局位置。
为了找到使村庄到邮局的最大距离最小的邮局位置，可以选择中位数位置的村庄来建造邮局。具体算法步骤如下：
对给定的坐标 $ x_1 < x_2 < ldots < x_n $ 进行排序（本题已满足排序条件）。
判断 $ n $ 的奇偶性：
– 如果 $ n $ 是奇数，选择第 $ frac{n + 1}{2} $ 个村庄作为邮局的位置。
– 如果 $ n $ 是偶数，选择第 $ frac{n}{2} $ 个或第 $ left( frac{n}{2} + 1
ight) $ 个村庄作为邮局的位置都可以，任选其一即可。
这样选择的原因是中位数能使到各个点的最大距离最小，从而保证了算法的最优性。
该算法的时间复杂度主要取决于排序操作，如果使用高效的排序算法（如快速排序、归并排序），时间复杂度为 $ O(n log n) $；若已经排好序，则时间复杂度为 $ O(1) $。
45、在笛卡尔平面中，有几种不同的方法来定义两点 p1(x1, y1) 和 p2(x2, y2) 之间的距离。特别地，曼哈顿距离定义为 dM(p1, p2) = |x1 – x2| + |y1 – y2|。证明 dM 满足每个距离函数都必须满足的以下公理：对于任意两点 p1 和 p2，dM(p1, p2) ≥0，并且当且仅当 p1 = p2 时，dM(p1, p2) = 0。
因为绝对值具有非负性，即
|x1−x2|≥0，|y1−y2|≥0|x1−x2|≥0，|y1−y2|≥0，
所以
|x1−x2|+|y1−y2|≥0|x1−x2|+|y1−y2|≥0，
也就是
dM(p1,p2)≥0dM(p1,p2)≥0。
当且仅当
|x1−x2|=0|x1−x2|=0 且
|y1−y2|=0|y1−y2|=0
时，
dM(p1,p2)=0dM(p1,p2)=0。
由
|x1−x2|=0|x1−x2|=0 可得
x1=x2x1=x2，
由
|y1−y2|=0|y1−y2|=0 可得
y1=y2y1=y2，
此时
p1=p2p1=p2；
反之，若
p1=p2p1=p2，即
x1=x2x1=x2 且
y1=y2y1=y2，
那么
|x1−x2|=0|x1−x2|=0 且
|y1−y2|=0|y1−y2|=0，
所以
dM(p1,p2)=0dM(p1,p2)=0。
因此，
dM(p1,p2)≥0dM(p1,p2)≥0 对于任意两点
p1p1 和
p2p2 成立，
并且
dM(p1,p2)=0dM(p1,p2)=0 当且仅当
p1=p2p1=p2。
46、在笛卡尔平面中，有几种不同的方法来定义两点p1(x1, y1)和p2(x2, y2)之间的距离。特别地，曼哈顿距离定义为dM(p1, p2) = |x1 – x2| + |y1 – y2|。证明dM满足每个距离函数都必须满足的以下公理：dM(p1, p2) = dM(p2, p1)。
根据曼哈顿距离的定义，
dM(p1,p2)=|x1−x2|+|y1−y2|dM(p1,p2)=|x1−x2|+|y1−y2|
dM(p2,p1)=|x2−x1|+|y2−y1|dM(p2,p1)=|x2−x1|+|y2−y1|
因为绝对值的性质 $|a – b| = |b – a|$，所以有：
|x1−x2|=|x2−x1||x1−x2|=|x2−x1|
|y1−y2|=|y2−y1||y1−y2|=|y2−y1|
因此，
dM(p1,p2)=dM(p2,p1)dM(p1,p2)=dM(p2,p1)
47、最近点对问题可以在k维空间中提出，其中两点p′(x′1, …, x′k)和p′′(x′′1, …, x′′k)之间的欧几里得距离定义为d(p′, p′′) = √(∑(s = 1到k)(x′s – x′′s)²)。k维最近点对问题的蛮力算法的时间效率类别是什么？
该算法的时间效率类别为Θ(n²)，与二维情况相同，因为蛮力算法需要计算每对不同点之间的距离，基本操作次数的计算与维度k无关，主要取决于点的数量n，计算次数为(n – 1)n，属于Θ(n²)。
48、求以下集合的凸包并确定其极点（如果有的话）：一段曲线。
曲线段的凸包是连接该曲线段两个端点的线段，其极点是曲线段的两个端点。
49、求以下集合的凸包并确定其极点（如果有的话）：一个圆
圆的凸包是其自身，其极点是圆周上的所有点。
50、找出下列集合的凸包并确定其极点（如果有的话）：六边形的边界。
该集合的凸包是由六边形边界所围成的区域，其极点是六边形的六个顶点。
51、求以下集合的凸包并确定其极点（如果有的话）：一个五边形
该五边形的凸包就是其自身，极点为五边形的五个顶点。
52、编写一个程序来实现最近点对问题的蛮力算法。
以下是使用 Python 实现最近点对问题的蛮力算法的代码：
import math
def BruteForceClosestPair(P):
d = float('inf')
n = len(P)
for i in range(n - 1):
for j in range(i + 1, n):
xi, yi = P[i]
xj, yj = P[j]
dist = math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
d = min(d, dist)
return d
# 示例使用
points = [(1, 2), (3, 4), (5, 6), (7, 8)]
print(BruteForceClosestPair(points))
这段代码定义了一个函数
BruteForceClosestPair
，它接受一个点列表
P
作为输入，通过双重循环计算每对点之间的欧几里得距离，并返回最小距离。
53、考虑以下线性规划问题的小实例：在约束条件x + y ≤4、x + 3y ≤6、x ≥0、y ≥0下最大化3x + 5y。在笛卡尔平面中绘制该问题的可行域，可行域定义为满足问题所有约束条件的点集。
可行域是通过两条直线 $ x + y = 4 $ 和 $ x + 3y = 6 $ 下方的半平面与笛卡尔平面第一象限（由非负约束 $ x geq 0 $、$ y geq 0 $ 定义）的交集得到。
该可行域是一个凸多边形，其顶点为：
$ (0, 0) $
$ (4, 0) $
$ (0, 2) $
$ (3, 1) $
其中，$ (3, 1) $ 是直线 $ x + y = 4 $ 和 $ x + 3y = 6 $ 的交点，通过求解以下线性方程组得到：
{x+y=4 x+3y=6{x+y=4 x+3y=6
54、考虑线性规划问题的以下小实例：在约束条件x + y ≤4、x + 3y ≤6、x ≥0、y ≥0下，最大化目标函数3x + 5y。使用以下定理求解此优化问题：具有非空有界可行域的线性规划问题总有一个解，该解可在其可行域的某个顶点处找到。
线性规划问题求解
确定可行域的顶点
令 $ x = 0 $，$ y = 0 $
，得到顶点 $ (0, 0) $。
令 $ x = 0 $
，代入 $ x + 3y = 6 $，解得 $ y = 2 $，得到顶点 $ (0, 2) $。
令 $ y = 0 $
，代入 $ x + y = 4 $，解得 $ x = 4 $，得到顶点 $ (4, 0) $。
联立 $ x + y = 4 $ 和 $ x + 3y = 6 $
：
– 将 $ x = 4 – y $ 代入 $ x + 3y = 6 $，得：
4−y+3y=6⇒2y=2⇒y=1,x=34−y+3y=6⇒2y=2⇒y=1,x=3
– 得到顶点 $ (3, 1) $。
代入目标函数求值
将各顶点坐标代入目标函数 $ 3x + 5y $ 求值：
对于顶点 $ (0, 0) $：$ 3 imes 0 + 5 imes 0 = 0 $
对于顶点 $ (0, 2) $：$ 3 imes 0 + 5 imes 2 = 10 $
对于顶点 $ (4, 0) $：$ 3 imes 4 + 5 imes 0 = 12 $
对于顶点 $ (3, 1) $：$ 3 imes 3 + 5 imes 1 = 14 $
结论
比较这些值，最大值为
14
。
因此，该线性规划问题的最优解是：
– $ x = 3 $，$ y = 1 $
– 目标函数的最大值为
14
。
55、假设能在常量时间内生成适合放入背包的物品子集的每个值，那么背包问题穷举搜索算法的效率类别是什么？
该穷举搜索算法的效率类别是Θ(2ⁿ)。
56、概述旅行商问题的穷举搜索算法。
问题建模
：用加权图对问题建模，图的顶点代表城市，边的权重表示距离，问题转化为找到图的最短哈密顿回路。
假设起始顶点
：不失一般性，假设所有回路都从一个特定顶点开始和结束。
生成排列
：通过生成 $ (n – 1) $ 个中间城市的所有排列来得到所有可能的旅行路线。
计算长度
：计算每个排列对应的旅行路线长度。
找到最短路线
：在所有计算出的路线长度中找出最短的路线。
优化
：由于存在一些仅方向不同的路线对，可通过选择两个中间顶点（如 $ b $ 和 $ c $），只考虑 $ b $ 排在 $ c $ 之前的排列，将顶点排列数量减半，但即使如此，当 $ n $ 较大时，穷举搜索方法仍然不实用。
57、概述一个算法，用于确定由邻接矩阵表示的连通图是否具有欧拉回路。该算法的效率类别是什么？
# 算法步骤
1. **检查图是否连通**
可以使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历图，若能访问到所有顶点，则图是连通的。
2. **检查每个顶点的度数**
通过邻接矩阵计算每个顶点的度数：
- 对于无向图，顶点的度数是邻接矩阵中该顶点对应行（或列）的元素之和。
- 对于有向图，需分别计算入度和出度。
3. **判断是否满足欧拉回路条件**
- 对于无向图，所有顶点的度数都为偶数。
- 对于有向图，每个顶点的入度等于出度。
## 效率类别
- 检查连通性的时间复杂度为 **O(V + E)**，其中 V 是顶点数，E 是边数。
- 计算顶点度数的时间复杂度为 **O(V²)**（因为使用邻接矩阵）。
- 因此，整个算法的时间复杂度为 **O(V²)**。
58、概述背包问题的穷举搜索算法。
穷举搜索算法解决背包问题的步骤为：
生成给定的 $ n $ 个物品集合的所有子集；
计算每个子集的总重量，以确定可行子集（即总重量不超过背包容量的子集）；
在可行子集中找出价值最大的子集。
59、解释如何应用穷举搜索来解决分配问题。
可将分配问题的可行解描述为n元组⟨j₁, …, jₙ⟩，其中第i个分量表示第i行中所选元素的列（即分配给第i个人的工作编号）。
分配问题的要求意味着可行分配与前n个整数的排列之间存在一一对应关系。
因此，穷举搜索解决分配问题的方法是：
生成整数1, 2, …, n的所有排列
通过对成本矩阵中相应元素求和来计算每个分配的总成本
最后选择总和最小的那个分配
60、如果我们将稀疏图定义为满足 |E| ∈O(|V |) 的图，对于这类图，使用邻接矩阵实现的深度优先搜索（DFS）和使用邻接表实现的 DFS，哪种实现的时间效率更高？
使用邻接表实现的 DFS 时间效率更高。因为对于稀疏图，邻接矩阵实现 DFS 的时间复杂度为 Θ(|V²|)，而邻接表实现 DFS 的时间复杂度为 Θ(|V| + |E|)，当 |E| ∈ O(|V|) 时，邻接表实现的复杂度更优。
61、判断正误：广度优先搜索（BFS）可以像深度优先搜索（DFS）一样，用于检查图的连通性和无环性。
正确
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
