探索算法世界：Algorithms Unplugged深度解析

需积分: 10 77 浏览量更新于2024-07-18 1 收藏 5.75MB PDF 举报

"Algorithms Unplugged英文版PDF" 《Algorithms Unplugged》是一本关于算法设计的书籍，由Berthold Vöcking、Helmut Alt、Martin Dietzfelbinger、Rudiger Reischuk、Christian Scheideler、Heribert Vollmer和Dorothea Wagner等专家共同编辑。这本书深入浅出地介绍了算法的核心概念和它们在信息技术中的应用。算法是计算机科学的基础，它们定义了计算机处理信息和执行任务的方式。随着科技的飞速发展，许多创新和成就都离不开算法的支撑。从科学研究到医学突破，从生产流程优化到物流、交通、通信和娱乐行业，算法都扮演着至关重要的角色。高效的算法不仅使个人电脑能够运行具有前卫功能的新一代游戏，而且在科学研究中也起到了关键作用，例如人类基因组的测序就离不开算法的革新，这些新算法极大地提高了计算速度，使得原本不可能的任务变得可能。《Algorithms Unplugged》这本书可能涵盖了以下内容： 1. 基础算法：包括排序算法（如冒泡排序、快速排序、归并排序等）、搜索算法（如二分查找）以及图论中的经典算法（如最短路径算法Dijkstra、最小生成树Prim或Kruskal）。 2. 数据结构：如栈、队列、链表、树、图和哈希表等，它们是实现高效算法的关键。 3. 动态规划：用于解决具有重叠子问题和最优子结构的问题，例如背包问题、最短路径问题等。 4. 贪心算法：通过每一步选择局部最优解来寻找全局最优解的方法，适用于某些特定问题。 5. 分治策略：将大问题分解为小问题，然后分别解决，再组合成原问题的解，如归并排序和快速排序的实现。 6. 回溯法与分支限界：用于在大量可能性中找到最优解的方法，常见于组合优化问题。 7. 图论算法：如网络流问题、最大匹配问题和旅行商问题等。 8. 概率和随机化算法：利用随机数和概率理论设计算法，可以提高效率或得到近似解。该书可能通过实例和直观的解释，帮助读者理解复杂的算法思想，无需依赖复杂的编程环境，旨在让读者在“拔掉插头”（unplugged）的情况下也能理解和掌握算法。对于计算机科学的学生和对算法感兴趣的读者来说，这是一本极好的学习资源，它有助于提升对算法设计和分析的理解，从而更好地应对实际问题。

Binary Search

Thomas Seidl and Jost Enderle

RWTH Aachen University, Aachen, Germany

Where has the new Nelly CD gone? I guess my big sister Linda with her craze

for order has placed it in the CD rack once again. I’ve told her a thousand

times to leave my new CDs outside. Now I’ll have to check again all 500 CDs

in the rack one by one. It’ll take ages to go through all of them!

Okay, if I’m lucky, I might possibly ﬁnd the CD sooner and won’t have to

check each cover. But in the worst case, Linda has lent the CD to her friend

again: then I’ll have to go through all of them and listen to the radio in the

end.

Aaliyah, AC/DC, Alicia Keys . . . hmmm, Linda seems to have sorted the

CDs by artist. Using that, ﬁnding my Nelly CD should be easier. I’ll try right

in the middle. “Kelly Family”; must have been too far to the left; I have to

search further to the right. “Rachmaninov”; now that’s too far to the right,

let’s shift a bit further to the left . . . “Lionel Hampton.” Just a little bit to

the right . . . “Nancy Sinatra” . . . “Nelly”!

Well, that was quick! With the sorting, jumping back and forth a few

times will suﬃce to ﬁnd the CD! Even if the CD hadn’t been in the rack,

this would have been noticed quickly. But when we have, say, 10,000 CDs, I’ll

probably have to jump back and forth a few hundred times to examine the

CDs. I wonder if one could calculate that.

B. V¨ocking et al. (eds.), Algorithms Unplugged,

DOI 10.1007/978-3-642-15328-0

 Springer-Verlag Berlin Heidelberg 2011

8 Thomas Seidl and Jost Enderle

The same holds true for a recursive deﬁnition of binary search: Instead of

executing the loop repeatedly (iterative implementation), the function calls

itself in the function body:

The function BinSearchRecursive returns the position of “key” in array

“A” between “left” and “right”

1 function BinSearchRecursive (A, key, left, right)

2 if left > right return not found

3 middle := (left + right)/2 // ﬁnd the middle, round the result

4 if A[middle] = key then return middle

5 if A[middle] > key then

6 return BinSearchRecursive (A, key, left, middle − 1)

7 if A[middle] < key then

8 return BinSearchRecursive (A, key, middle + 1, right)

As before, A is the array to be searched through, “key” is the key to

be searched for, and “left” and “right” are the left and right borders of the

searched region in A, respectively. If the element “Nelly” has to be found in

an array “rack” containing 500 elements, we have the same function call, Bin-

SearchRecursive (rack, “Nelly”, 1, 500). However, instead of pushing the

borders towards each other iteratively by a program loop, the BinSearchRe-

cursive function will be called recursively with properly adapted borders. So

we get the following sequence of calls:

BinSearchRecursive (rack, “Nelly”, 1, 500)

BinSearchRecursive (rack, “Nelly”, 251, 500)

BinSearchRecursive (rack, “Nelly”, 251, 374)

BinSearchRecursive (rack, “Nelly”, 313, 374)

BinSearchRecursive (rack, “Nelly”, 344, 374)

···

Number of Search Steps

Now the question remains, how many search steps do we actually have to

perform to ﬁnd the right element? If we’re lucky, we’ll ﬁnd the element with

the ﬁrst step; if the searched element doesn’t exist, we have to keep jumping

until we have reached the position where the element should be. So, we have

to consider how often the list of elements can be cut in half or, conversely,

how many elements can we check with a certain number of comparisons. If

we presume the searched element to be contained in the list, we can check

two elements with one comparison, four elements with two comparisons, and

eight elements with only three comparisons. So, with k comparisons we are

able to check 2 · 2 · ··· · 2(k times) = 2

elements. This will result in ten

comparisons for 1,024 elements, 20 comparisons for over a million elements,

剩余416页未读，继续阅读

annieyan

粉丝: 0
资源: 3

探索算法世界：Algorithms Unplugged深度解析

传感器系统算法英文版PDF资料

2015年Mahmoud Parsian的《Data Algorithms》英文电子版

《算法导论》第三版英文版：Introduction to Algorithms 3rd Edition

algorithms 4th英文版pdf

.pdf 算法 中文版Algorithms 英文版 第4版Robert Sedgewick

accuracy and stability of numerical algorithms（英文版）

算法导论[Introduction.to.Algorithms] 英文版

Data Structures and Algorithms in Java 英文第4版pdf檔

Algorithms in C 英文版

Algorithms 算法概论 英文版

最新资源

.pdf 算法中文版Algorithms 英文版第4版Robert Sedgewick

Algorithms 算法概论英文版