刷题中对一些算法思想的理解

刷题过程中,对一些大家熟知的概念有了自己的体会,这是一个满足的体验啊。比如,理解一些思路为何能上升为”思想”,如分治思想。

以排序的快排、归并为例,最开始我们了解它们一般都是先接触它们的思路,

快排的思路

在一个序列中选择一个数为中轴 pivot,将小于等于中轴数的放到左边,大于它的放在右边;
不断对左边和右边的子序列作以上操作。

归并思路

排序一个序列,先不断的划分为两部分别排序,再将左右两边的有序序列合并; 不断对左右两边分别以上操作。

从归并再反思快排,我们发现,归并比快排要”懒”一些啊~

快排一次划分将序列分成了三部分,且将三者排好序,而归并一次划分仅将序列分为两部分,两者没有急着排序,而是优哉游哉将排序放到 不可划分之后。

快排像一个勤奋或急功近利的年轻人,每次操作,便急着将中轴数放到最终的位置,付出的”比较汗水”很多,每个数会比较n-1次;

归并像一个深谋远虑的老者,不急不躁,将比较的操作放到”合并”流程中,使得每次”比较”的结果都能给后面的”比较”助力,为什么这么说呢?
比如合并 [1,3,5] 与[2,4,6],左边的1与右边2比较后,发现1比2小,且右边是递增的有序序列,故1也一定比2之后的数据小,也就是无需再与 2之后的数比较,那么至少省了2次比较呀。

而且啊,基于快排”排序不稳定”,归并”排序稳定”,它们年轻人、老者的形象似乎更加立体了。

在不同的场景下,它们各有千秋,在现实的世界中,无疑还是年轻人干活的场景更多一点呀。

在啰嗦完它们不同点之后,我们来找它们的共同点,为何他俩能在众多排序算法中更加惹人注目呢? 我想,它俩相比与一些暴力蛮干的排序相比, 它俩都散发着”分治”智慧。遇到”排列好一堆数”的复杂问题,能寻见其间的共通,将复杂问题化为共通部分的叠加子问题,求解简单的子问题,便能 可求得原问题之解。

具体上,再看上面提及的两个排序思路,都是”分治思想”应用,仅是划分角度的不同。
快排,将问题化为,排序一个数和两个子序列简单子问题,排序一个数与两个序列可省力多了,毕竟只要花O(n);
归并,似乎”分为治之”更为明显,遇到问题,若非问题规模为1,即1个数无需排序,否则统统将问题规模减半,令人惊艳的在于,合并的过程中, 子问题的答案能够为父问题求解提供帮助,从而在整体求解上起飞。

分而治之,基于问题本就由一个个子问题构成的客观事实,拆解问题便是我们认识世界的过程,可以说,分而治之是我们与生俱来解决问题思路。

另外,若能将问题拆分后,若子问题之间不依赖,并发执行,也是可以提高效率吧。

前天遇到了一道题,颠倒二进制, 引出上文~