算法对数据科学很重要，没有系统地学习过也没关系。 本文介绍了三种基本算法。 这可能有助于我们在数据科学的道路上走得更远。
算法是数据科学不可缺少的一部分。 虽然大多数数据科学家在学校没有上适当的算法课，但并不影响算法的重要性。
许多企业把数据结构和算法作为数据科学家面试的一部分。
许多人怀疑向数据科学家提出这样的问题有什么用。 我认为数据结构的问题可以看作是编程能力测试。
我们在生命的各个阶段都会面临各种各样的能力测试，但这并不是判断人的完美指标，但似乎没有其他更好的标准。 那么，为什么不能通过标准的算法测试来判断人的编程能力呢？
不是开玩笑，要通过算法测试你必须付出足够的热情，所以你可能想花时间学习算法。
本文快速跟进算法学习，选取数据科学家不可缺少的几个算法概念，并以易于理解的方式进行介绍。
递归/记忆
递归即函数在其自身的定义内适用。 简单地说，递归就是函数调用自己。 在谷歌搜索引擎中搜索“recursion”时，您会发现一些有趣的事情。
我不知道你是否理解了这个笑话。 递归对初学者来说有点可怕，但实际上很容易理解。 一旦了解，你就会发现那是一个美丽的概念。
我认为说明递归的最好例子是计算数字的阶乘：
可以很容易地看出，deffactorial(n ) : IFN==0: return1returnn * Factorial ) n-1 )阶乘是递归函数。
在工业(n (n )工业) n-1 )中，如何过渡到编程呢？
递归调用函数通常包含两个部分：
基线条件(基本情况) )递归停止的条件； 递归条件：函数调用自己，并逐渐向基线条件移动。 我们要解决的很多问题是递归的，数据科学也是如此。
例如，决策树是二叉树，树算法通常是递归的。 或者，我们经常使用sort 负责sort的算法被称为mergesort，是递归算法。 另一种是二分搜索(binary search )，涉及到找出数组中的某个元素。
既然对递归有了基本的了解，接下来让我们来找出第n个平稳的葡萄酒数(Fibonacci Number )。 温和的葡萄酒数列的各个数字(温和的葡萄酒数)是前面两个数字之和。 最简单的例子是1，1，2，3，5，8，…答案是：
deffib(n ) : IFN=1:返回1返回光纤) n-1 ) fib ) n-2 )你发现那个问题了吗？
在计算FIB(n=7)时，函数将执行两次FIB )5)、三次FIB )4)、五次FIB )3)。 n的值越大，调用相同数字的次数就越多，递归函数被多次计算。
那么能做得更好吗？ 当然。 可以稍微修改实现，添加词典，然后在此方法中添加一些存储过程。 现在，每次计算数字时都会更新这个memo词典。 当这个数字再次出现时，我们不需要再次计算，可以直接根据memo词典得出结果。 添加记忆称为记忆(Memoization )。
emo=def Fib _ Memo (n ) : Ifninmemo 3360返回Memo [ n ] IFN=1: Memo=1返回1 Memo=Fib _ Memo
这个有用吗？
上图显示了n为不同值时的运行时间比较。 可以看出，无记忆平稳的葡萄酒数列执行时间呈指数级增加，记忆函数执行时间呈线性。
动态计划
递归本质上是一种自上而下的方法。 计算温和的葡萄酒数n时，我们从n到n-2和n-1执行递归调用……
然后动态地
规划中，我们采用自下而上的方法。它本质上是一种迭代地写递归的方式。我们首先计算 fib(0) 和 fib(1)，然后使用之前的结果生成新结果。
def fib_dp(n): dp_sols = {0:1,1:1} for i in range(2,n+1): dp_sols[i] = dp_sols[i-1] + dp_sols[i-2] return dp_sols[n]
上图对比了动态规划和记忆的运行时间。我们可以看到，二者均为线性，但是动态规划的速度要稍微快一些。
为什么？因为在该案例中，动态规划仅对每个子问题执行了一次调用。
二分搜索
假设存在一个有序数组，我们想从中找出一个数字。我们可以按照线性方式逐个检查每个数字，直到找到目标数字。而问题在于，如果该数组包含数百万个元素，则这一过程会很长。这里我们可以使用二分搜索。
找出数字 37。这片数字海洋里有 3.7 万亿条小鱼，而我们的目标是找出其中一条。（图源：http://mathwarehouse.com/programming）
# Returns index of target in nums array if present, else -1 def binary_search(nums, left, right, target): # Base case if right >= left: mid = int((left + right)/2) # If target is present at the mid, return if nums[mid] == target: return mid # Target is smaller than mid search the elements in left elif nums[mid] > target: return binary_search(nums, left, mid-1, target) # Target is larger than mid, search the elements in right else: return binary_search(nums, mid+1, right, target) else: # Target is not in nums return -1nums = [1,2,3,4,5,6,7,8,9]print(binary_search(nums, 0, len(nums)-1,7))
还有一个基于递归算法的高级案例，该案例中我们利用有序数组这一事实。这里我们递归地查看中间元素，确认我们想要在中间元素的左侧还是右侧执行搜索。这就使得每一步的搜索空间减少了二分之一。
因而，该算法的运行时间是 O(logn)，而不是线性搜索的 O(n)。
这有多大作用呢？下图展示了二者的运行时间对比情况。我们可以看到二分搜索要比线性搜索快很多。
结论
本文介绍了构成编程基础的几个有趣算法。
这些算法隐藏在数据科学面试最常被问的问题背后，了解它们或许可以帮助你得到心仪的工作。
当然不学这些算法也不影响你在数据科学道路上的前进，不过你可以学着玩玩，或许可以提高编程技能呢。
end.
作者:Rahul Agarwal
扫描下方二维码报名参加课程
