新鲜 / 健康 / 便利 / 快速 / 放心
需要提前知道的知识点:时间复杂度
例题:给你一个数组a[N],要求求出最大连续和。
最不需要动脑子的算法,暴力枚举就可以了。
算法分析:使用了3重for循环,时间复杂度达到了比较恐怖的O(n3)这就意味着如果n在比较大的时候暴力枚举的算法就会使用比较久的时间,而这样的算法我们并不喜欢。
用前缀和稍微优化一下
算法分析:在这里,我们使用前缀和数组qzh[i]来代表a[1]~a[i]的和,这样我们就可以优化掉暴力枚举中的最后一层循环从而把时间复杂度降低为O(n2)
二分递归优化
算法分析:这里的时间复杂度为O(nlogn)级别复杂度,可以通过解答树证明,递归的解答树高为logn,对于树的每一层我们加起来扫描了1~n,因此总的时间复杂度为nlogn。相比前面两种算法,第三种的速度显然是最快的。
最简单的排序,时间复杂度为O(n2),一般来说不使用,除非某些特定的题目。由于是很简单的基础知识所以在这里就不多提了。
归并排序分为3步:划分问题、递归求解、合并问题
看上去和上文的二分递归优化挺像,实际上很多算法的优化思路都是大同小异的。
其中第一步和第二步都是没什么难度的,当分到的区间长度为1时就自然而然排好序了,那么关键就是如何把两个区间合并。
合并方法:创建一个新的数组,每次对比两个区间的最小值,把最小值放进新数组。时间复杂度为O(nlogn)
这里紫书作者偷了个懒没有详细介绍快速排序,快速排序相比归并排序省去了t数组的空间,减小了空间复杂度。这里也就找一篇博客来让大家看看快速排序的定义吧。
博客:快速排序概念介绍(作者:李小白~)
排序的意义之一,就是为查找带来便利。如果一个数组是乱序的,那么对于一个数字的查找一定是O(n)级别的时间复杂度。那么,排好序之后难道我们就可以优化时间复杂度了吗?答案是肯定的。
我们先来玩一个小游戏:你在心里想一个1~1000的数,我可以保证在10次以内猜到——前提是你必须告诉我我猜的数比你想的大一些、小一些或刚好相等。
猜的方法非常的简单,我先猜500,如果你告诉我大了,我锁定范围为1~ 499,然后再猜250……。每一次猜测我能把范围缩短一半,由于log21000<10。10次是足够我猜到正确答案的。
这就是二分查找的基本思路,时间复杂度为O(logn)。
c++STL中的lower_bound()、upper_bound()函数的实现原理就是二分查找。
注意: 在算法的时间优化中,我们在很多时候会用二分的思想来把O(n)的时间复杂度优化为O(logn)。因此二分的思想是非常重要的。
紫书把贪心算法放在了这里介绍,但其实贪心算法介绍起来还是比较抽象的。
其实贪心算法理解起来并不难,就像你如果能那走n个物品里的m个物品,那么你如果要利益最大化,就每一次都拿一个最贵的物品。这就是顾名思义的贪心算法。
1.符合贪心策略:所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2.最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
血的教训: 在实际问题中,我们往往能很容易想到使用贪心算法去解题,但是…往往是不对的。并且更加坑爹的是往往样例是能过的…(经典贪心只能过样例)。因此在实际解题中慎用贪心算法,使用前一定要多加思考避免造成不必要的损失。
作者:Avalon Demerzel,喜欢我的博客就点个赞吧,更多紫书知识点请见作者专栏《紫书学习笔记》