关于前端:分而治之算法

分而治之

原文链接：https://note.noxussj.top/?source=sifo

什么是分而治之？

在咱们后面有学习过一系列数据结构、以及相干的一些算法，蕴含排序、搜索算法。而本次学习的分而治之它不是数据结构，也不是一种算法，而是算法设计中的一种办法，能够了解为是一种思维。咱们能够利用这种思维去设计很多种算法。

分而治之是将一个问题分成多个和原问题类似的小问题，递归解决小问题，再将后果合并以解决原来的问题。次要分成三个局部，别离是 “ 分 ”、” 递归解决 ”、” 合 ”。

根底案例

场景一

归并排序

• 分：把数组从两头一分为二
• 解：递归地对两个子数组进行归并排序
• 合：合并有序子数组

首先它会把一个大的数组拆分成两个小的数组，再别离对每个小数组又进行拆分成两个小数组，以此类推，最初把单个元素的小数组全副进行合并并排序，最初组成一个大数组从而解决了问题。

归并排序是一个典型的分而治之思维的利用。

场景二

疾速排序

• 分：选基准，按基准把数组分成两个子数组
• 解：递归地对两个子数组进行疾速排序
• 合：对两个子数组进行合并

步骤如同归并排序相似。

场景三

二分搜寻同样具备 “ 分 ”、” 解 ”、” 合 ” 的个性。

原文链接：https://note.noxussj.top/?source=sifo