认识达内从这里开始

算法的学习与应用是每一位软件编程开发程序员都需要熟练掌握的一个编程知识点，而本文我们就通过案例分析来简单了解一下，常见的编程开发算法都有哪些类型。

1.分治算法(DivideandConquer)

分而治之(DAC)本身并不是一个特定的算法，而是在深入研究其他主题之前需要了解的重要算法类别。它用于解决可以划分为与原始问题相似但规模较小的子问题的问题。然后DAC递归地求解它们，后合并结果以找到问题的解决方案。

它分为三个阶段：

划分——将问题分解为子问题;

用递归解决子问题;

合并——子问题的结果到终解决方案中。

它是干什么用的?

分治算法(DAC)的一种实际应用是使用多个处理器进行并行编程，因此子问题在不同的机器上执行。

DAC是许多算法的基础，例如快速排序、合并排序、二分搜索或快速乘法算法。

特性

每个DAC问题都可以写成一个递推关系;因此，必须找到停止递归的基本情况;

它的复杂度是T(n)=D(n)+C(n)+M(n)，这意味着每个阶段都有不同的复杂度，具体取决于问题。

2.排序算法(SortingAlgorithms)

排序算法用于根据元素上的比较运算符重新排列给定元素(来自数组或列表)。当我们提到一个排序数组时，我们通常会想到升序(比较运算符是“<”)。排序有多种类型，具有不同的时间和空间复杂度。其中一些是基于比较的，有些则不是。以下是流行/有效的排序方法：

冒泡排序(BubbleSort)

冒泡排序是简单的排序算法之一。它基于相邻元素之间的重复交换(如果它们的顺序错误)。它是稳定的，它的时间复杂度是O(n²)并且它需要O(1)辅助空间。

计数排序(CountingSort)

计数排序不是基于比较的排序。它基本上是使用每个元素的频率(一种散列)，确定小值和大值，然后在它们之间迭代以根据其频率放置每个元素。它在O(n)中完成，空间与数据范围成正比。如果输入范围不明显大于元素数量，则它是有效的。

快速排序(QuickSort)

快速排序是分而治之的一个应用。它基于选择一个元素作为枢轴(一个、后一个或中间值)，然后交换元素以将枢轴放置在所有小于它的元素和所有大于它的元素之间。它没有额外的空间和O(n*logn)时间复杂度——基于比较的方法的佳复杂度。

归并排序(MergeSort)

归并排序也是一个分而治之的应用程序。它将数组分成两半，对每一半进行排序，然后合并它们。它的时间复杂度也是O(n*logn)，所以它也像QuickSort一样超快，但不幸的是它需要O(n)额外空间来同时存储两个子数组，后合并它们。

基数排序(RadixSort)

基数排序使用计数排序作为子程序，因此它不是基于比较的算法。我们怎么知道CS是不够的?假设我们必须对[1,n²]中的元素进行排序。使用CS，我们需要O(n²)。我们需要一个线性算法——O(n+k)，其中元素在[1,k]范围内。它从不重要的一个(单位)开始，到重要的(十、百等)对元素进行逐位排序。额外空间(来自CS)：O(n)。

3.搜索算法(SearchingAlgorithms)

搜索算法旨在检查数据结构中元素的存在，甚至返回它。有几种搜索方法，但这里是受欢迎的两种：

线性搜索(LinearSearch)

该算法的方法非常简单：您从数据结构的一个索引开始搜索您的值。您将它们一一比较，直到您的值和当前元素相等。如果该特定值不在DS中，则返回-1。

时间复杂度：O(n)

二分查找(BinarySearch)

BS是一种基于分而治之的高效搜索算法。不幸的是，它只适用于排序的数据结构。作为一种DAC方法，您连续将DS分成两半，并将搜索中的值与中间元素的值进行比较。如果它们相等，则搜索结束。无论哪种方式，如果您的值大于/小于它，搜索应该继续在右/左半部分。

时间复杂度：O(logn)

4.埃氏筛法(SieveofEratosthenes)

给定一个整数n，打印所有小于或等于n的素数。

Eratosthenes筛法是解决这个问题的有效的算法之一，它完美地适用于小于10.000.000的n。

该方法使用频率列表/映射来标记[0,n]范围内每个数字的素数：如果x是素数，则ok[x]=0，否则ok[x]=1。

我们开始从列表中选择每个素数，并用1标记列表中的倍数——这样，我们选择未标记的(0)数。后，我们可以在O(1)中轻松回答任意数量的查询。

算法在许多应用中都是必不可少的，但我们可以进行一些优化。先，我们很容易注意到2是的偶素数，因此我们可以单独检查它的倍数，然后在范围内迭代以找到从2到2的素数。其次，很明显，对于数字x，我们之前在迭代2、3等时已经检查了2x、3x、4x等。这样，我们的乘数检查for循环每次都可以从x²开始。后，即使这些倍数中有一半是偶数，而且我们也在迭代奇素数，因此我们可以在倍数检查循环中轻松地从2x迭代到2x。

空间复杂度：O(n)

时间复杂度：O(n*log(logn))用于算法，O(n)用于优化算法。

5.字符串匹配算法(Knuth-Morris-Pratt)

给定长度为n的文本和长度为m的模式，找出文本中所有出现的模式。

Knuth-Morris-Pratt算法(KMP)是解决模式匹配问题的有效方法。

天真的解决方案基于使用“滑动窗口”，每次设置新的起始索引时，我们都会比较字符与字符，从文本的索引0开始到索引nm。这样，时间复杂度是O(m*(n-m+1))~O(n*m)。

KMP是对朴素解决方案的优化：它在O(n)中完成，并且当模式具有许多重复的子模式时效果佳。因此，它也使用滑动窗口，但不是将所有字符与子字符串进行比较，而是不断寻找当前子模式的长后缀，这也是它的前缀。换句话说，每当我们在某些匹配后检测到不匹配时，我们就已经知道下一个窗口文本中的某些字符。因此，再次匹配它们是没有用的，因此我们重新开始匹配文本中具有该前缀后的字符的相同字符。我们怎么知道我们应该跳过多少个字符?好吧，我们应该构建一个预处理数组，告诉我们应该跳过多少个字符。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。