【紫书第八章】算法的时间优化设计

一、算法的时间优化

需要提前知道的知识点：时间复杂度

例题：给你一个数组a[N],要求求出最大连续和。

1.暴力枚举起点和终点(下策)

最不需要动脑子的算法，暴力枚举就可以了。

算法分析：使用了3重for循环，时间复杂度达到了比较恐怖的O(n³)这就意味着如果n在比较大的时候暴力枚举的算法就会使用比较久的时间，而这样的算法我们并不喜欢。

2.暴力枚举+前缀和优化(中策)

用前缀和稍微优化一下

算法分析：在这里，我们使用前缀和数组qzh[i]来代表a[1]~a[i]的和，这样我们就可以优化掉暴力枚举中的最后一层循环从而把时间复杂度降低为O(n²)

3.二分递归分治法(上策)

二分递归优化

算法分析：这里的时间复杂度为O(nlogn)级别复杂度，可以通过解答树证明，递归的解答树高为logn，对于树的每一层我们加起来扫描了1~n，因此总的时间复杂度为nlogn。相比前面两种算法，第三种的速度显然是最快的。

4.小结

• 在上面的时间复杂度计算中，我们计算出来的时间复杂度都是近似的，我们在高等数学中求极限值的时候往往只会抓住主要矛盾。例如（n³+n）在n取无限大的时候，我们就可以不用考虑+n的影响而只用考虑n³的作用了。我们在时间复杂度的计算上也是一样的。
• 在平时的做题中，哪怕是最简单的问题也有可能因为数据的巨大而变得棘手，因此我们在日常学习中需要不断地思考能否对自己的算法进行优化。

二、再谈排序与搜索

1.冒泡排序

最简单的排序，时间复杂度为O(n²),一般来说不使用，除非某些特定的题目。由于是很简单的基础知识所以在这里就不多提了。

2.归并排序

归并排序分为3步：划分问题、递归求解、合并问题
看上去和上文的二分递归优化挺像，实际上很多算法的优化思路都是大同小异的。

其中第一步和第二步都是没什么难度的，当分到的区间长度为1时就自然而然排好序了，那么关键就是如何把两个区间合并。

合并方法：创建一个新的数组，每次对比两个区间的最小值，把最小值放进新数组。时间复杂度为O(nlogn)

3.快速排序

这里紫书作者偷了个懒没有详细介绍快速排序，快速排序相比归并排序省去了t数组的空间，减小了空间复杂度。这里也就找一篇博客来让大家看看快速排序的定义吧。
博客：快速排序概念介绍（作者：李小白~）

4.二分查找(重点)

排序的意义之一，就是为查找带来便利。如果一个数组是乱序的，那么对于一个数字的查找一定是O(n)级别的时间复杂度。那么，排好序之后难道我们就可以优化时间复杂度了吗？答案是肯定的。

我们先来玩一个小游戏：你在心里想一个1~1000的数，我可以保证在10次以内猜到——前提是你必须告诉我我猜的数比你想的大一些、小一些或刚好相等。

猜的方法非常的简单，我先猜500，如果你告诉我大了，我锁定范围为1~ 499，然后再猜250……。每一次猜测我能把范围缩短一半，由于log₂1000<10。10次是足够我猜到正确答案的。

这就是二分查找的基本思路，时间复杂度为O(logn)。

c++STL中的lower_bound()、upper_bound()函数的实现原理就是二分查找。

注意： 在算法的时间优化中，我们在很多时候会用二分的思想来把O(n)的时间复杂度优化为O(logn)。因此二分的思想是非常重要的。

三、贪心算法

紫书把贪心算法放在了这里介绍，但其实贪心算法介绍起来还是比较抽象的。

1.概念介绍

• 狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解。
• 广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。

其实贪心算法理解起来并不难，就像你如果能那走n个物品里的m个物品，那么你如果要利益最大化，就每一次都拿一个最贵的物品。这就是顾名思义的贪心算法。

2.使用条件

• 1.符合贪心策略：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
  对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

• 2.最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

3.局限性

• 不能保证求得的最后解是最佳的；
• 不能用来求最大或最小解问题；
• 只能求满足某些约束条件的可行解的范围。

血的教训： 在实际问题中，我们往往能很容易想到使用贪心算法去解题，但是…往往是不对的。并且更加坑爹的是往往样例是能过的…（经典贪心只能过样例）。因此在实际解题中慎用贪心算法，使用前一定要多加思考避免造成不必要的损失。

作者：Avalon Demerzel，喜欢我的博客就点个赞吧，更多紫书知识点请见作者专栏《紫书学习笔记》