算法是数据科学不可或缺的一部分。尽管许多数据科学家在学习时没有参加适当的算法课程，但这确实很重要。比如很多公司在面试数据科学家的时候，都会问到数据结构和算法的问题。现在，问题是，问数据科学家这样的问题有什么用。我对这个问题的回答是，数据结构题可以看做是对编码能力的考验。我们都在生活的不同阶段进行过能力倾向测试，但这些测试并不能完美地判断一个人，而且很少有测试能做到。那么，为什么不用标准的算法测试来判断一个人的编码能力呢？因为算法和测试都不是死板的，你总可以在前面总结的基础上进行改进和创新，总可以用不同的算法来应对这些测试。但这并不意味着不掌握基础就可以撼动算法的基础。牢牢掌握基本算法的概念和应用，始终是优秀数据科学家必备的素质。本文将帮助数据科学家快速回顾相关研究，并以通俗易懂的方式介绍一些基本的算法概念。1.递归/记忆化递归就是把定义好的函数应用到自己的定义中。简而言之，递归是一个调用自身的函数。当你用谷歌搜索递归时，你会遇到一个小问题。刚开始学习数据科学的人可能会觉得递归有点难，但其实很好理解。一旦你理解了它，它就是一个伟大的概念。解释递归的最好例子是计算一个数的阶乘。deffactorial(n):ifn==0:return1returnn*factorial(n-1)很容易看出factorial是一个递归函数。Factorial(n)=n*Factorial(n-1)那么这如何转化为编程呢？被递归调用的函数通常由两部分组成：基线条件——终止递归的条件。递归公式——向基线条件发展的公式。很多问题解决到最后，就是递归问题。这也适用于数据科学。例如，决策树是二叉树，而树算法通常是递归的。或者，以我们经常使用的排序为例。排序算法称为mergesort，它本身是一种递归算法。另一种是二进制搜索，它涉及在数组中查找元素。现在我们了解了递归的基础知识，让我们尝试找到第n个斐波那契数。斐波那契数列是一系列数字，其中每个数字（斐波那契数）是前两个数字的总和。最简单的数字序列是1、1、2、3、5、8等。求第n个斐波那契数，可以用下面的代码：deffib(n):ifn<=1:return1returnfib(n-1)+fib(n-2)但是，你有没有发现问题呢？如果您尝试计算fib(n=7)运行fib(5)两次，运行fib(4)三次，运行fib(3)五次。随着n变大，对同一个数字进行多次调用，递归函数一次又一次地计算它。稍微改变我们的实现，添加一个字典来为这个方法添加一些存储。现在，每次计算一个数字时，都会更新这个备忘录字典。如果再次出现相同的数字，则无需重新计算，直接从备忘词典中获取结果即可。这种增加存储空间的方式称为记忆化。memo={}deffib_memo(n):ifninmemo:returnmemo[n]ifn<=1:memo[n]=1return1memo[n]=fib_memo(n-1)+fib_memo(n-2)returnmemo[n]通常，我我会先写递归代码，如果它重复调用相同的参数，我会添加另一个字典来记忆。这有帮助吗？图中是不同n值的运行时间对比。可以看出，没有记忆的斐波那契函数的运行时间呈指数增长，而记忆函数的运行时间是线性的。2.动态规划的递归本质是一种自上而下的方法。比如计算斐波那契数n时，就是从n开始，然后递归调用n-2和n-1，以此类推。在动态规划中，我们采用自下而上的方法。这本质上是一种迭代编写递归的方法。首先计算fib(0)和fib(1)，然后使用以前的结果生成新结果。defib_dp(n):dp_sols={0:1,1:1}foriinrange(2,n+1):dp_sols[i]=dp_sols[i-1]+dp_sols[i-2]returndp_sols[n]上图是“动态规划”和“记忆化”运行时间的比较。可以看出都是线性的，但是动态规划要快一点。为什么？因为在这种情况下，动态规划只对每个子问题进行一次调用。关于开发动态规划的贝尔曼如何定下“动态规划”这个名称，有一个有趣的故事：“动态规划”这个名称从何而来？50年代的数学研究形势不是很好。好的。当时，华盛顿有一位非常有趣的先生，名叫威尔逊，他是国防部长。事实上，他对研究这个词怀有病态的恐惧和仇恨。那我可以给它起什么名字呢？首先，我想到了“计划”、“决策”、“思考”。但出于各种原因，“计划”并不是一个好词。所以，我决定用“策划”这个词。我想传达的概念是，这是动态的、多层次的、时变的。所以，我觉得动态规划是个好名字，一箭双雕。这是连国会议员都不会反对的事情。所以我决定使用这个名字。3、二分查找假设存在一个排序好的数字组合，要从这个数组中找出一个数字。我们可以使用线性搜索，一个一个地检查每个数字，直到找到一个特定的数字。问题是如果数组包含数百万个元素，这种方法会花费很长时间。在这种情况下，可以使用二进制搜索方法。资料来源：Discovery37-海洋中有3.7万亿条鱼，它们正在寻找其中的一条#Returnsindexoftargetinnumsarrayifpresent,else-1defbinary_search(nums,left,right,target):#Basecaseifright>=left:mid=int((left+right)/2)#Iftargetispresentathemid,returnifnums[mid]==target:returnmid#Targetissmallerthanmidsearchtheelementsinleftelifnums[mid]>target:returnbinary_search(nums,left,mid-1,target)#Targetislargerthanmid,searchtheelementsinrightelbinse,_return(right,target)else:#Targetisnotinnumsreturn-1nums=[1,2,3,4,5,6,7,8,9]print(binary_search(nums,0,len(nums)-1,7))这是一个基于递归的高级示例算法。利用数组排序的优势，递归查看中间元素，看是要向中间元素的左边还是右边查找。这在每一步将搜索空间减少了2倍。因此，二分搜索算法的运行时间是O(logn)而不是线性搜索的O(n)。这是做什么的？下面是运行时间的比较。我们可以看到，与线性搜索相比，二分搜索速度相当快。当n=10000时，二分查找大约需要13步，线性查找需要10000步。结束语本文触及了构成编程基础的一些算法，虽然它们很基础，但同样令人兴奋。数据科学家在面试时经常被问及这些算法，深入了解它们可能会帮助你找到理想的工作。尽管您可以在不学习这些算法的情况下在数据科学方面取得进步，但您可以将学习它们作为一种有趣的方式来培养您的兴趣并在此过程中提高您的编程技能。以一石二鸟，何乐而不为？
