很高兴能和大家一起共同学习算法导论这本书。笔者将在业余时间把算法导论后面的题解以博文的形式展现出来希望能得到大家的支持谢谢。如果有可能我会做一些教学视频免费的供大家观看。
练习题选自算法导论中文第三版第6页中的练习。
1.1-1 给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。这个问题有俩个子问题。我一一解答：
(1) 首先是排序，日常需要排序的地方很多，例如今日微博热搜等等这个不用细说了。
(2)但是关于第二个问题我需要多写一点。
第一这本书的翻译的地方有误，凸壳在这里指的是计算几何中的多边形凸包问题。
下面摘选自百度百科。
⒈对于一个集合D，D中任意有限个点的凸组合的全体称为D的凸包。 ⒉对于一个集合D，所有包含D的凸集之交称为D的凸包。 可以证明，上述两种定义是等价的 概念 示例图（一） 示例图（一） 1 点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 2 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。 数学定义：设S为欧几里得空间 的任意子集。包含S的最小凸集称为S的凸包，记作conv(S)