没有合适的资源?快使用搜索试试~ 我知道了~
首页算法基础与应用
算法基础与应用
需积分: 9 0 下载量 184 浏览量
更新于2024-07-24
收藏 1.95MB PDF 举报
"《算法概论Algorithms》是由S.Dasgupta、C.H.Papadimitriou和U.V.Vazirani三位作者共同编写的,旨在介绍算法的基本概念和重要应用的一本书。该书涵盖了从基础的数学运算到复杂的图论问题,以及随机化算法和最短路径计算等多个领域。" 这本书首先通过序言引入了算法在图书和实际问题中的重要性,并以斐波那契数列作为示例,展示了算法在解决实际问题中的作用。接下来,书中引入了大O记号,这是分析算法复杂度的重要工具,用于描述算法运行时间的增长速率。 在"算法与数字"这一章中,作者深入讨论了基本的算术运算、模运算和素数测试。此外,还涉及了密码学的基础,包括加密算法,以及一种叫做均匀哈希的方法,用于减少冲突并提高数据结构的性能。 "分治算法"章节则探讨了如何将复杂问题分解为更小的部分来解决,如高效的乘法算法、递归关系、归并排序、寻找中位数以及快速傅里叶变换等。这些算法在数据处理和计算中扮演着关键角色。 "图的分解"部分介绍了图论在算法中的应用,解释了为什么我们需要研究图,并详细阐述了无向图和有向图的深度优先搜索,以及如何识别强连通组件。这些是理解网络和复杂系统结构的基础。 "图中的路径"章节进一步深化了对图的理解,探讨了距离计算、广度优先搜索、边的权重、迪杰斯特拉算法(Dijkstra's algorithm)以及在存在负权边时的最短路径问题。这些内容对于路由、网络优化和物流规划等问题至关重要。 这本书通过丰富的例子和练习题,引导读者逐步掌握算法设计和分析的基本技巧,是一本适合初学者和进阶者的经典教材。它不仅讲解了理论,还强调了算法的实际应用,有助于读者在理解和运用算法方面打下坚实基础。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/6636863/bg10.jpg)
Figure 0.2 Which running time is better?
1 2 3 4 5 6 7 8 9 10
0
10
20
30
40
50
60
70
80
90
100
n
2n+20
n
2
Now another algorithm comes along, one that uses f
3
(n) = n + 1 steps. Is this better
than f
2
? Certainly, but only by a constant factor. The discrepancy between f
2
and f
3
is tiny
compared to the huge gap between f
1
and f
2
. In order to stay focused on the big picture, we
treat functions as equivalent if they differ only by multiplicative constants.
Returning to the definition of big-O, we see that f
2
= O(f
3
):
f
2
(n)
f
3
(n)
=
2n + 20
n + 1
≤ 20,
and of course f
3
= O(f
2
), this time with c = 1.
Just as O(·) is an analog of ≤, we can also define analogs of ≥ and = as follows:
f = Ω(g) means g = O(f )
f = Θ(g) means f = O(g) and f = Ω(g).
In the preceding example, f
2
= Θ(f
3
) and f
1
= Ω(f
3
).
Big-O notation lets us focus on the big picture. When faced with a complicated function
like 3n
2
+ 4n + 5, we just replace it with O(f(n)), where f(n) is as simple as possible. In this
particular example we’d use O(n
2
), because the quadratic portion of the sum dominates the
rest. Here are some commonsense rules that help simplify functions by omitting dominated
terms:
1. Multiplicative constants can be omitted: 14n
2
becomes n
2
.
2. n
a
dominates n
b
if a > b: for instance, n
2
dominates n.
3. Any exponential dominates any polynomial: 3
n
dominates n
5
(it even dominates 2
n
).
16
![](https://csdnimg.cn/release/download_crawler_static/6636863/bg11.jpg)
4. Likewise, any polynomial dominates any logarithm: n dominates (log n)
3
. This also
means, for example, that n
2
dominates n log n.
Don’t misunderstand this cavalier attitude toward constants. Programmers and algorithm
developers are very interested in constants and would gladly stay up nights in order to make
an algorithm run faster by a factor of 2. But understanding algorithms at the level of this
book would be impossible without the simplicity afforded by big-O notation.
17
![](https://csdnimg.cn/release/download_crawler_static/6636863/bg12.jpg)
Exercises
0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case
f = Θ(g)).
f(n) g(n)
(a) n − 100 n − 200
(b) n
1/2
n
2/3
(c) 100n + log n n + (log n)
2
(d) n log n 10n log 10n
(e) log 2n log 3n
(f) 10 log n log(n
2
)
(g) n
1.01
n log
2
n
(h) n
2
/ log n n(log n)
2
(i) n
0.1
(log n)
10
(j) (log n)
log n
n/ log n
(k)
√
n (log n)
3
(l) n
1/2
5
log
2
n
(m) n2
n
3
n
(n) 2
n
2
n+1
(o) n! 2
n
(p) (log n)
log n
2
(log
2
n)
2
(q)
P
n
i=1
i
k
n
k+1
0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c
2
+ ··· + c
n
is:
(a) Θ(1) if c < 1.
(b) Θ(n) if c = 1.
(c) Θ(c
n
) if c > 1.
The moral: in big-Θ terms, the sum of a geometric series is simply the first term if the series is
strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the
series is unchanging.
0.3. The Fibonacci numbers F
0
, F
1
, F
2
, . . . , are defined by the rule
F
0
= 0, F
1
= 1, F
n
= F
n−1
+ F
n−2
.
In this problem we will confirm that this sequence grows exponentially fast and obtain some
bounds on its growth.
(a) Use induction to prove that F
n
≥ 2
0.5n
for n ≥ 6.
(b) Find a constant c < 1 such that F
n
≤ 2
cn
for all n ≥ 0. Show that your answer is correct.
(c) What is the largest c you can find for which F
n
= Ω(2
cn
)?
0.4. Is there a faster way to compute the nth Fibonacci number than by fib2 (page 13)? One idea
involves matrices.
We start by writing the equations F
1
= F
1
and F
2
= F
0
+ F
1
in matrix notation:
F
1
F
2
=
0 1
1 1
·
F
0
F
1
.
Similarly,
F
2
F
3
=
0 1
1 1
·
F
1
F
2
=
0 1
1 1
2
·
F
0
F
1
18
![](https://csdnimg.cn/release/download_crawler_static/6636863/bg13.jpg)
and in general
F
n
F
n+1
=
0 1
1 1
n
·
F
0
F
1
.
So, in order to compute F
n
, it suffices to raise this 2 × 2 matrix, call it X, to the nth power.
(a) Show that two 2 × 2 matrices can be multiplied using 4 additions and 8 multiplications.
But how many matrix multiplications does it take to compute X
n
?
(b) Show that O(log n) matrix multiplications suffice for computing X
n
. (Hint: Think about
computing X
8
.)
Thus the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is
just O(log n), as compared to O(n) for fib2. Have we broken another exponential barrier?
The catch is that our new algorithm involves multiplication, not just addition; and multiplica-
tions of large numbers are slower than additions. We have already seen that, when the complex-
ity of arithmetic operations is taken into account, the running time of fib2 becomes O(n
2
).
(c) Show that all intermediate results of fib3 are O(n) bits long.
(d) Let M(n) be the running time of an algorithm for multiplying n-bit numbers, and assume
that M(n) = O(n
2
) (the school method for multiplication, recalled in Chapter 1, achieves
this). Prove that the running time of fib3 is O(M (n) log n).
(e) Can you prove that the running time of fib3 is O(M(n))? (Hint: The lengths of the num-
bers being multiplied get doubled with every squaring.)
In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit
integers faster than O(n
2
). Do you think this is possible? (The answer is in Chapter 2.)
Finally, there is a formula for the Fibonacci numbers:
F
n
=
1
√
5
1 +
√
5
2
!
n
−
1
√
5
1 −
√
5
2
!
n
.
So, it would appear that we only need to raise a couple of numbers to the nth power in order to
compute F
n
. The problem is that these numbers are irrational, and computing them to sufficient
accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of
raising these irrational numbers to the nth power. If you know your linear algebra, you should
see why. (Hint: What are the eigenvalues of the matrix X?)
19
![](https://csdnimg.cn/release/download_crawler_static/6636863/bg14.jpg)
20
剩余317页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/1bf66e0f16604870b6abb339ac4f5872_z_p_liu363912650.jpg!1)
z_p_liu363912650
- 粉丝: 4
- 资源: 30
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述:模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成:理论与算法
- 基于语义元的相似度计算方法研究:改进与有效性验证
- 网格梯度多密度聚类算法:去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型:有效提升系统状态预测
- 煤矿安全评价:信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN:统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)