《算法技术手册》一1.1 理解问题

简介: 本节书摘来华章计算机《算法技术手册》一书中的第1章 ,第1.1节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

第1章

用算法的眼光去看问题

算法真的是非常重要!算法的选择会对软件的性能产生巨大影响。本书将指导你学习一系列的算法,例如搜索和排序,还会介绍一些算法经常采用的策略,例如分治或贪心。希望从此之后,你能够灵活运用这些算法来改善软件的性能。
自“计算”出现之后,数据结构便一直与算法紧密相关。本书将介绍一些基本的数据结构,并展示如何使用这些数据结构来高效地处理数据。
“在选择算法时,你需要做什么?”我们将在接下来的章节中探究这个问题的答案。

1.1 理解问题

设计算法的第一步就是理解将要解决的问题。以一个计算几何领域的简单问题为例:给定一个二维点集P(见图1-1),想象着用一个橡皮圈把这些点围起来,松开之后,这个橡皮圈的形状就是凸包(能够把点集P所有的点全部包围起来的最小凸形)。那么,现在的任务就是编写一个算法,针对一个给定的二维点集,计算它的凸包。
仔细观察点集P的凸包就会发现,连接P中任何两点的线段都位于这个凸包内。假设,我们把凸包中的点按顺时针排好,不难发现,这个凸包其实是由h个顺时针排列的点L0, L1, ..., Lh-1组成,如图1-2所示。每三个相邻的点Li, Li+1, Li+2组成一个向右拐的线条。
有了这样的信息,也许你可以手工画出任意点集的凸包,但是否能写出一个算法呢(给出一系列循序渐进的指令,并且能够高效地计算出任意点集的凸包)?
有趣之处在于,这个凸包问题貌似并不属于任何众所周知的算法范畴。而且,似乎也并没有任何线性时间的排序算法能够按照从左到右顺时针对点进行排序。与此类似,要找到凸包上的一条线段并不难,因为这条线段一定会使得平面上剩余的n-2个点都位于其“右侧”,但也没有显而易见的搜索算法可用。
2017_09_19_142633
图1-1:平面上由15个点组成的示例点集
2017_09_19_142749
图1-2:图1-1中点的凸包

相关文章
|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
7天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
9天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
12天前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
13 0
|
14天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python。
|
15天前
|
存储 人工智能 算法
RAG技术的高级应用和算法
文章主要探讨了RAG技术的高级应用和算法,系统化地整理了各种方法。
|
15天前
|
机器学习/深度学习 数据采集 算法
基于机器学习的推荐算法构建技术详解
【6月更文挑战第4天】本文详述了构建基于机器学习的推荐算法,特别是协同过滤方法。从用户和物品相似性的角度,解释了用户-用户和物品-物品协同过滤的工作原理。涵盖了数据准备、预处理、特征工程、模型训练、评估优化及结果展示的构建流程。推荐算法在电商、视频和音乐平台广泛应用,未来将受益于大数据和AI技术的进步,提供更智能的推荐服务。
|
20天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python
|
28天前
|
存储 算法 搜索推荐
【大数据分析与挖掘技术】Mahout推荐算法
【大数据分析与挖掘技术】Mahout推荐算法
23 0

热门文章

最新文章