《Python算法教程》——2.7 练习题

简介:

本节书摘来自异步社区《Python算法教程》一书中的第2章,第2.7节,作者[挪威]Magnus Lie Hetland(赫特兰), 凌杰 译,更多章节内容可以访问云栖社区“异步社区”公众号查看。

2.7 练习题

2-1. 当我们用Python中的list构建一个多维数组时,通常需要使用循环来完成(或某种与list推导式等效的技术),为什么不能用表达式[[0]10]10来创建一个10×10的数组呢?这样做会有什么问题吗?

2-2. 让我们来做个假设(也许会有点不切实际):如果我们允许在分配内存时出现未初始化的情况(也就是说,这块内存中还保有上一次被使用时留下的“垃圾数据”),并且分配内存也只需要常数时间。这时如果您想创建一个含有n 个整数的数组,并且希望跟踪其每一项——看看它是处于非初始化状态,还是您已经在它里面保存过一个数字了。这种检查操作也是可以在常数时间内完成的。那么,我们究竟应该怎样做,才能保证它在常数时间内完成它的初始化操作呢?(以及应该如何在常数时间里完成一个空邻接数组的初始化操作,以避免其成为一个以平方级时间为最小运行时间的操作?)

2-3. 请证明O 与Ω的性质正好相反,即如果f = O (g ),那么g = Ω(f ),反之亦然。

2-4. 对数通常有各自不同的底数,但在算法学上,我们往往并不会太在意它。为了明白其中的原因,我们可以来考虑一下这个等式:logbn= (logan )/(logab)。首先,您知道这个等式为什么成立吗?其次,为什么它能告诉我们不需要去操心对数的底数问题?

2-5. 请证明任何指数级操作(Θ(kn ),其中k > 1)的增长都要快于多项式级操作(Θ(nj ),其中j > 0)。

2-6. 请证明任何多项式操作(Θ(nk ),其中k 为任意常数且k > 0)的渐近增长都要快于对数级操作(Θ(lg n ))。(值得注意的是,这里的多项式中包括根数在内,如平方根(k = 0.5)等)。

2-7. 请研究或推算一下Python list类型上各个操作的渐近复杂度,如索引、元素项赋值、顺序反转、元素的追加及插入(最后两项我们在list的黑盒子专栏中已经讨论过了)。如果我们改用链表类型来实现这些操作会有什么不同?请以list.extend为例加以说明。

2-8. 请证明表达式Θ(f ) + Θ(g ) = Θ(f + g ) and Θ(f ) · Θ(g ) = Θ(f · g )成立。另外,您也可以试试是否能证明max(Θ(f ), Θ(g )) = Θ(max(f , g )) = Θ(f + g )成立。

2-9. 在附录C中,您会找到一组与树有关的、带编号的陈述句,请证明它们是等效的。

2-10. 假设T 是一棵有根树,它至少应包含三个节点,并且每个内部节点下面又正好都有两个子节点。那么,如果T 上有n 个叶节点,树上到底应有多少个节点呢?

2-11. 请证明一个DAG可以由任何形式的(底层)结构组成。换言之,任何(无向)图结构都可以成为一个DAG的底层图结构。或者说,对于任何给定的图结构,我们都可以通过调整其边线方向,从中产生出一个有向图,而它正好是一个DAG。

2-12. 请考虑下面这种图结构的表示法:我们使用字典类型,设置其每个键为两个节点的元组,然后将该元组的值设置为边的权值,如W[u, v] = 42。请问:该表示法有什么优点和缺点?您有办法弥补这些缺点吗?

相关文章
|
20天前
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
5天前
|
算法 数据可视化 Python
Python贝叶斯推断Metropolis-Hastings(M-H)MCMC采样算法的实现
Python贝叶斯推断Metropolis-Hastings(M-H)MCMC采样算法的实现
|
5天前
|
数据可视化 算法 数据挖掘
PYTHON实现谱聚类算法和改变聚类簇数结果可视化比较
PYTHON实现谱聚类算法和改变聚类簇数结果可视化比较
|
6天前
|
算法 数据可视化 Python
Python中LARS和Lasso回归之最小角算法Lars分析波士顿住房数据实例
Python中LARS和Lasso回归之最小角算法Lars分析波士顿住房数据实例
11 0
|
6天前
|
机器学习/深度学习 算法 Python
使用Python实现集成学习算法:Bagging与Boosting
使用Python实现集成学习算法:Bagging与Boosting
17 0
|
7天前
|
缓存 算法 Python
python算法对音频信号处理Sonification :Gauss-Seidel迭代算法
python算法对音频信号处理Sonification :Gauss-Seidel迭代算法
|
10天前
|
算法 数据可视化 数据挖掘
使用Python实现DBSCAN聚类算法
使用Python实现DBSCAN聚类算法
150 2
|
11天前
|
存储 算法 安全
Python加密算法有哪些?有什么作用?
这些加密算法的作用在于保护敏感数据的隐私和完整性。它们可以用于数据传输、存储、身份验证和数字签名等领域。通过加密,可以确保数据在传输和存储过程中不被未经授权的人访问或篡改。同时,数字签名可以用于验证数据的来源和完整性,防止数据被篡改或冒充。不同的加密算法在不同的应用场景中起到不同的作用,选择合适的算法取决于安全需求和性能要求。 买CN2云服务器,免备案服务器,高防服务器,就选蓝易云。百度搜索:蓝易云
6 0
|
12天前
|
算法 数据可视化 数据挖掘
使用Python实现K均值聚类算法
使用Python实现K均值聚类算法
16 1
|
13天前
|
算法 Python
使用Python实现朴素贝叶斯算法
使用Python实现朴素贝叶斯算法
15 0