算法gydF4y2Ba
算法是一个过程,它接受输入,遵循一组特定的步骤,然后产生输出。通常,算法定义输入和输出之间所需的关系。例如,如果我们试图解决的问题是对一副牌进行排序,这个问题可以定义如下:gydF4y2Ba
问题gydF4y2Ba:对输入排序。gydF4y2Ba
输入gydF4y2Ba:一套5张卡片。gydF4y2Ba
输出gydF4y2Ba: 5张输入卡片的集合,已排序。gydF4y2Ba
过程gydF4y2Ba:由算法设计者决定!gydF4y2Ba
最后一部分非常重要,它是算法的主要部分。而且,作为一名算法设计师,您可以做任何想要产生所需输出的事情!想一些你可以对手中的5张卡片进行分类的方法,然后点击下面查看更多的想法。gydF4y2Ba
我们可以把它们抛到空中,然后再捡起来。也许它们会被分类。如果没有,我们可以一次又一次地尝试,直到它成功(剧透:这是一个糟糕的算法)。gydF4y2Ba
我们可以从左到右逐个排序。假设我们的手是{2,4,1,9,8}。2和4已经排好序了。然后是1。它应该在4之前,它应该在2之前。现在我们有{1 2 4 9 8}。9在正确的位置,因为它比它左边的牌高,4。但是8是错误的,因为它小于9,所以我们把它放在9前面。现在,我们有{1 2 4 8 9},做完了。这就是所谓的gydF4y2Ba插入排序gydF4y2Ba.gydF4y2Ba
我们可以一次把它们从左到右排序。我们的手还是{2,4,1,9,8}。2和4是好的。4和1需要交换,所以现在我们有{2,1,4,9,8}。4和9是好的。9和8应该交换,所以现在我们有{2,1,4,8,9}。我们得从头再来一遍,但这没问题。我们看第一对,发现2和1需要交换,现在我们有{1 2 4 8 9},我们做完了。这就是所谓的gydF4y2Ba冒泡排序gydF4y2Ba.gydF4y2Ba
有无数种方法可以对这张牌进行分类!有些是伟大的,大多数是可怕的。作为算法设计者,你要做出一个伟大的算法。gydF4y2Ba
算法的研究涉及到在给定输入和目标的情况下,找到实现预期输出的最佳方法。学习算法是成为一名成功的计算机程序员的必要条件,了解算法可以帮助你了解计算机是如何工作的。所以,如果你想学习编码,学习算法是绝对必要的。gydF4y2Ba
内容gydF4y2Ba
算法和计算机gydF4y2Ba
尽管算法在现代计算机出现之前就存在了,但它们是计算和技术的核心。你在任何技术上所做的一切都依赖于算法,因为它们告诉技术该做什么。算法决定了你能否以可容忍的速度上网。想象一下,你正在访问一个网站,这个网站有很多未排序的内容要展示给你。如果每次你访问它的时候,它都随机选择一个内容顺序,然后把这个顺序扔掉,如果它不正确,你就得等上几分钟,几个小时,甚至几天才能加载你的网页!gydF4y2Ba
学习计算机科学和计算机编程总是涉及到算法,因为算法的学习教会你像机器一样思考,这样你就能以尽可能最好的方式编程。如果你想学习如何编写应用程序,制作网站,或做数据分析,你需要知道算法,这样你的代码将运行得更快和正确。gydF4y2Ba
在理论方面,许多更简单的算法早已被发现并被大量研究,但仍有许多领域有待研究。例如,在理论计算机科学中,一个挥之不去的问题是,是否gydF4y2BaP = NPgydF4y2Ba,或者换句话说,“这些问题可以很快解决。gydF4y2Ba验证gydF4y2Ba通过电脑可以快速的gydF4y2Ba解决了gydF4y2Ba由计算机吗?”目前,我们并不这么认为。但如果这是真的,那么计算机和技术将经历一个巨大的速度增长,我们都将从中受益。然而,这也意味着现代gydF4y2Ba密码学gydF4y2Ba不安全,任何黑客都可以轻易破解世界上任何系统的密码!gydF4y2Ba
随着计算机的发展,计算机的应用也随之发展。为了执行能够实现这些应用程序的算法,计算机科学家需要一种表示和存储数据的方法。如果我们想将一组卡片输入计算机程序,我们将如何存储这些数据?我们如何将它输入算法?在早期,仅仅用计算机位(0和1)来表示数据就足够了。但是,这种方法不可能持久,因为它太困难和耗时。gydF4y2Ba
数据结构gydF4y2Ba是答案。他们的发明和研究是与算法并行的,而且常常与算法一起教授。例如,卡片排序算法可以gydF4y2Ba数组gydF4y2Ba用数字来代表卡片。随着时间的推移,越来越多的数据结构被发明出来,它们允许算法设计与它们一起进步。有了这些,推理、开发和研究算法就变得容易得多。gydF4y2Ba
算法的特性gydF4y2Ba
在设计和分析算法时,要记住3个主要属性。gydF4y2Ba
算法属性:gydF4y2Ba
- 时间复杂度。这是一个算法完成所需的时间,通常使用gydF4y2Ba大O符号gydF4y2Ba将其输入作为自变量。例如,如果我们想搜索排序后的卡片gydF4y2Ba 卡片,我们可以用对数时间,时间复杂度是gydF4y2Ba .gydF4y2Ba
- 空间的复杂性。这是算法在执行过程中使用的空间(在计算机内存中)。如果我们要排序gydF4y2Ba 卡片,我们需要做一个额外的数组gydF4y2Ba 对于每一张这样做的卡片,空间复杂度将是gydF4y2Ba .gydF4y2Ba
- 的正确性。当且仅当对每个输入都停止并输出正确的输出时,算法才是正确的。与你所想的相反,不正确的算法有时是有用的。例如,gydF4y2Ba部分正确的算法gydF4y2Ba只保证算法停止时,答案是正确的。gydF4y2Ba
算法可以用多种方式表达,你可以在Brilliant上的不同维基中找到其中的许多方法。gydF4y2Ba
下面是一些如何描述算法的例子:gydF4y2Ba
- 一个gydF4y2Ba高层次的描述gydF4y2Ba.这可以是描述算法的文本或散文形式:它是输入、输出和目标。一般来说,这并不涉及算法的实现细节。gydF4y2Ba
- 正式的定义gydF4y2Ba.正式的定义通常会以正式的数学术语给出算法的输入和输出。实现输出的过程也被正式地表示出来。这是一种更数学化的算法表示方式。gydF4y2Ba
- 伪代码gydF4y2Ba.这是一种松散形式化算法的方法,在学习算法时经常使用。有一般的实现细节;但是,为了不使事情复杂化,我们省略了特定于语言的细节。gydF4y2Ba
- 实现gydF4y2Ba.给定语言的实现将是计算机可以理解和运行的一段代码。实现了算法的目标和过程;然而,在实现中包含高级细节比较困难,因为计算机将拒绝纯文本。gydF4y2Ba
类型的算法gydF4y2Ba
算法有很多种,描述算法的语言也因教科书和人的不同而不同。一些算法标签描述了它们的功能,而另一些则描述了它们执行功能的过程。gydF4y2Ba
例如,有一种算法叫做gydF4y2Ba字符串匹配算法gydF4y2Ba;这些算法在较大的字符串或文本片段中查找输入字符串的出现情况。字符串匹配算法的一个例子是gydF4y2Ba- karp算法gydF4y2Ba,但还有更多。另一方面,描述算法解决问题的方法的标签的一个例子是gydF4y2Ba分治算法gydF4y2Ba.举个例子gydF4y2Ba二分查找gydF4y2Ba,它通过将输入分割成更小的片段来搜索已排序输入中的目标,直到找到目标为止。gydF4y2Ba
一个特定的算法可以跨越这两个类。例如,执行排序的排序算法gydF4y2Ba递归地gydF4y2Ba可以被描述为一个排序函数gydF4y2Ba或gydF4y2Ba一个递归函数。gydF4y2Ba
描述功能的标签:gydF4y2Ba
算法的标签gydF4y2Ba | 描述gydF4y2Ba |
排序算法gydF4y2Ba | 对可比输入列表进行排序。gydF4y2Ba |
图算法gydF4y2Ba | 执行基本的图算法,如搜索。gydF4y2Ba |
最短路径算法gydF4y2Ba | 求图中点之间的最短路径。gydF4y2Ba |
字符串匹配算法gydF4y2Ba | 在较大的文本中搜索输入字符串。gydF4y2Ba |
最大流算法gydF4y2Ba | 计算流量网络中的最大流量。gydF4y2Ba |
计算几何算法gydF4y2Ba | 可以用几何表示的算法的一个分支gydF4y2Ba |
数论算法gydF4y2Ba | 处理数论的算法,比如gydF4y2Ba肾小球囊性肾病gydF4y2Ba |
快速傅里叶变换算法gydF4y2Ba | 有效的算法执行gydF4y2Ba傅里叶变换gydF4y2Ba |
矩阵算法gydF4y2Ba | 对矩阵进行运算的算法gydF4y2Ba |
描述过程的标签:gydF4y2Ba
算法的标签gydF4y2Ba | 描述gydF4y2Ba |
分而治之gydF4y2Ba算法gydF4y2Ba | 将问题分解成更小的子问题,这些子问题可以重新组合得到答案。gydF4y2Ba |
贪心算法gydF4y2Ba | 通常返回次优答案的问题的简单、天真的方法gydF4y2Ba |
动态规划gydF4y2Ba算法gydF4y2Ba | 创建更小的子问题,其答案有助于解决越来越大的子问题。gydF4y2Ba |
递归gydF4y2Ba算法gydF4y2Ba | 这种算法不断地要求自己解决越来越小的问题,直到形成最终解决方案的基础gydF4y2Ba |
蛮力算法gydF4y2Ba | 一种解决问题的方法,它试图用更多的计算能力而不是优雅的方式来解决问题gydF4y2Ba |
回溯算法gydF4y2Ba | 算法构建部分候选解的集合,只有当它们变得不可能时才会忘记它们gydF4y2Ba |
概率和随机算法gydF4y2Ba | 使用任意形式随机化的算法(也称为非确定性算法)gydF4y2Ba |
近似算法gydF4y2Ba | 一些方法试图通过做近似来减少计算时间,得到最优答案的某个因素gydF4y2Ba |
多线程算法gydF4y2Ba | 运行在多个gydF4y2Ba线程gydF4y2Ba并行化工作gydF4y2Ba |
线性规划算法gydF4y2Ba | 通过使用输入的线性关系得到最优答案的解gydF4y2Ba |
设计一个算法gydF4y2Ba
在设计算法时,重要的是要记住,计算机不是无限快的,计算机内存也不是无限大的。这就是我们制作算法的原因。所以,也许你正在为一台计算机设计一种算法,它速度非常快,但内存却不多。也许您会在计算需求上做出一些让步,以便节省内存。gydF4y2Ba
但即使你从来不用担心速度和空间,你gydF4y2Ba仍然gydF4y2Ba需要设计一个好的算法。为什么?你需要设计一个好的算法,因为你需要知道算法会做你想让它做的事,一旦完成它就会停止。你需要知道它是正确的。gydF4y2Ba
功效gydF4y2Ba
的gydF4y2Ba功效gydF4y2Ba你所设计的算法gydF4y2Ba时间复杂度gydF4y2Ba和gydF4y2Ba空间复杂度gydF4y2Ba.在理想情况下,该算法在两方面都是有效的,但有时在两者之间存在权衡。为了达到平衡,设计师需要适当地权衡他们的需求。gydF4y2Ba
设计一个好的算法也取决于设计者。这样做需要理解算法以及现有算法,以指导您的设计过程。否则,他们可能会发现自己的算法很糟糕。gydF4y2Ba
两种算法以不同方式执行相同的精确物质可能具有巨大的疗效差异。例如,在排序中,gydF4y2Ba冒泡排序gydF4y2Ba需要gydF4y2Ba 在执行过程中。gydF4y2Ba快速排序gydF4y2Ba,另一方面,需要gydF4y2Ba 空间。对于使用这些算法的程序员来说,这意味着什么?为了简单起见,让我们假设输入只是1KB的数据(或8000位)。快速排序需要gydF4y2Ba 是冒泡排序的13倍。如果将其扩展到1GB甚至1TB的输入,那么这种差异就会变得非常明显,而且效率非常低。gydF4y2Ba
然而,值得注意的是,快速排序比冒泡排序运行得更快。同样,这是一个权衡,这取决于设计师理解权衡,并根据他们的需求优化设计。gydF4y2Ba
分析和评估算法gydF4y2Ba
算法的分析和评估是一个两步的过程。在分析部分,研究了算法的性质:时间/空间复杂度和正确性。描述算法的任何枚举方法gydF4y2Ba以上gydF4y2Ba,可以被研究。然而,该描述必须包含关于算法内部工作的足够信息,以提供其过程的清晰画面。gydF4y2Ba
一般来说,有几种方法可以描述时间复杂度。有gydF4y2Ba最好的gydF4y2Ba,gydF4y2Ba平均情况gydF4y2Ba,gydF4y2Ba最坏的gydF4y2Ba的算法。作为一个程序员,了解每种情况是很重要的,这样你才能完全理解你的算法将如何运行。关注哪种情况取决于您,但最坏情况下的性能通常被用作算法的基准。gydF4y2Ba
评价部分是更定性的,要求观察者自己对算法的有效性做出决定,因为它与其他类似算法有关。您可能会看到这个算法,并注意到它正在犯一些严重的错误,从而增加了它的运行时间。您可能还会发现,它的运行时间与完成相同任务的其他算法截然不同。无论哪种情况,评价结果都很差。gydF4y2Ba
让我们看看算法的伪代码,并尝试分析它的时间复杂度。的伪代码如下gydF4y2Ba插入排序gydF4y2Ba,一个基本的排序算法。它的输入是一个数组,gydF4y2Ba ,并返回相同的已排序数组。注意,这个伪代码假设索引为1(数组中的第一个索引是1,而不是0)。gydF4y2Ba
1 2 3 4 5 6 7 8gydF4y2BaInsertion_Sort(A) for j = 2 to j = A length: current = A[j] i = j - 1 while i > 0 and A[i] > current: A[i+1] = A[i] i = i - 1 A[i+1] = currentgydF4y2Ba
首先,让我们看看这段代码在做什么。我们有一个输入的数字数组gydF4y2Ba
[4, 2, 3, 7, 8]gydF4y2Ba
.该算法遍历该数组,从第二个元素开始,在本例中,gydF4y2Ba2gydF4y2Ba
.它调用这个数字gydF4y2Ba当前的gydF4y2Ba
.它在前面抓取索引gydF4y2Ba当前的gydF4y2Ba
,这是gydF4y2Ba1gydF4y2Ba
它的价值是gydF4y2Ba4gydF4y2Ba
,并设它等于gydF4y2Ba我gydF4y2Ba
.现在它想要移动gydF4y2Ba4gydF4y2Ba
到正确的位置。while循环说“while索引”gydF4y2Ba我gydF4y2Ba
大于0,而数字gydF4y2Ba2gydF4y2Ba
大于它左边的邻居,移动吗gydF4y2Ba2gydF4y2Ba
向左并递减gydF4y2Ba我gydF4y2Ba
1”。所以,gydF4y2Ba2gydF4y2Ba
移动到与算法目前看到的数字相对应的正确位置。gydF4y2Ba可以通过逐行查看这些代码来分析这些伪代码。在第二行,它有一个gydF4y2Bafor循环gydF4y2Ba从值2迭代到值a。length,也就是我们的输入大小,gydF4y2Ba 我们已经知道这个算法是gydF4y2Ba至少gydF4y2Ba与输入大小线性相关。换句话说,这个算法的运行时间至少是gydF4y2Ba 或gydF4y2Ba .gydF4y2Ba
for循环中的所有内容都必须执行gydF4y2Ba 所以我们可以忽略常数时间操作,比如第3、4和8行。相反,第5行是焦点必须转移的地方,因为它是另一个可迭代循环。gydF4y2Ba
的gydF4y2Bawhile循环gydF4y2Ba第5行类似于第2行的for循环,但它可以重复的次数是可变的。这个数字可以从1到gydF4y2Ba 这取决于数组最初的排序方式。如果输入数组为gydF4y2Ba
[2, 3, 4, 7, 8]gydF4y2Ba
,例如gydF4y2Ba而gydF4y2Ba
循环将只运行1次,因为每个元素都不大于其左边的元素。但是,如果输入是gydF4y2Ba[8, 7, 4, 3, 2]gydF4y2Ba
,则需要运行while循环gydF4y2Ba 次了。为了了解原因,让我们看看while循环每次迭代后的数组是什么样子的:gydF4y2Ba
1 2 3 4 5 5gydF4y2Ba0(输入)。[8、7、4、3、2]1:[7、8、4、3、2)2:[4、7、8、3、2)3:[2]3、4、7、8日4:[2、3、4、7、8)gydF4y2Ba
看看如何在gydF4y2Ba 和gydF4y2Ba 迭代的gydF4y2Ba
2gydF4y2Ba
必须在数组中移动吗?这是gydF4y2Ba 次了。gydF4y2Ba因此,第2行上的for循环进行迭代gydF4y2Ba 次了。第5行上的while循环遍历从gydF4y2Ba 来gydF4y2Ba 次了。所以,最佳运行时是gydF4y2Ba 当输入列表已经排序,最坏的情况是gydF4y2Ba 当它是逆序排列时。一般情况要理解起来有点棘手。基本上,我们希望输入数组中的任何元素都小于其左边元素的一半。一半的元素是静止的gydF4y2Ba 这仍然是gydF4y2Ba ,所以平均情况也是gydF4y2Ba .gydF4y2Ba
下面的伪代码表示一个算法,该算法接受一个可以包含正整数或字符串的元素数组作为输入。换句话说,输入是这样的gydF4y2Ba[42, 'a', 1, 'hello', 3]gydF4y2Ba
.gydF4y2Ba
输出数组的算法有以下属性:元素的输出在一个字符串和整数之间交替,每个元素是小于或等于前面的相同类型的元素(除了在位置1和2的元素,这是最大的各自的类型)。在计算机科学中,可以对字符串进行排序(例如,'b' > 'a')。如果输入没有相同数量的整数和字符串,则输出将包含比输入更多的元素。gydF4y2Ba
这个算法的运行时间是多少?gydF4y2Ba
对于本例,假设排序算法Reverse_Cheating_Sort(A)是一个常量gydF4y2Ba 操作。gydF4y2Ba
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25gydF4y2Ba |
|
艰难的算法gydF4y2Ba
典型的算法通常是有效的。它们运行的时间是多项式。换句话说,它们的运行时可以定义为gydF4y2Ba 对于一些输入gydF4y2Ba 和一些整数gydF4y2Ba .然而,有一类算法目前没有多项式时间解。一些著名的例子是gydF4y2Ba旅行推销员问题gydF4y2Ba或者是gydF4y2Ba集合覆盖问题gydF4y2Ba.gydF4y2Ba
这些问题被称为np完全问题,研究起来非常有趣。虽然还没有为它们发现多项式时间算法,但也没有人证明这一点gydF4y2Ba不能gydF4y2Ba做一个局外人,等待被发现。此外,如果只找到其中一个的解,就可以推断出gydF4y2Ba所有gydF4y2Ba其中!gydF4y2Ba
目前有各种各样的算法可以很好地近似解决这些问题。他们可能会使用gydF4y2Ba启发式gydF4y2Ba减少运行时间。然而,答案并不总是准确的,因此算法是不正确的。gydF4y2Ba
计算机科学领域包含许多值得探索的令人兴奋的领域。在理论和算法中,np完备性及其与其他算法的关系问题困扰了计算机科学家几十年,并且对技术和世界有许多重要的影响。gydF4y2Ba