知行编程网知行编程网  2022-05-02 11:00 知行编程网 |  隐藏边栏 |   抢沙发 |  2 
文章评分 0 次，平均分 0.0 ：

破解数据科学面试，这里有最常考的三种算法

来自 | towardsdatascience   作者 | Rahul Agarwal
转自 | 机器之心
算法对数据科学很重要，没有系统学习过也没关系。本文介绍了三种基本算法，或许可以帮助你在数据科学的道路上走得更远。

破解数据科学面试，这里有最常考的三种算法


算法是数据科学中不可或缺的一部分。尽管大部分数据科学家在上学时没有学过合适的算法课，但这并不影响算法的重要性。

很多企业将数据结构和算法作为数据科学家面试中的一部分。

而很多人疑惑，对数据科学家询问此类问题有何用处。我认为数据结构问题可被视为编程能力测试。

我们在生命的不同阶段会面临各种能力测试，尽管这并非判断一个人的完美指标，但似乎也没有其他更好的标准了。那么，为什么不能用标准算法测试来判断一个人的编程能力呢？

不开玩笑地说，你必须付出足够的热情才能够通过算法测试，因此，你或许想花一些时间学习算法。

本文将快速跟进算法学习，选取一些对数据科学家必不可少的算法概念，并用易于理解的方式展开介绍。

   递归/记忆

递归即函数在其自身定义内应用。简单来说，递归即函数调用自己。在谷歌搜索引擎中搜索「recursion」（递归）时，你会发现一些有意思的事。

破解数据科学面试，这里有最常考的三种算法


不知道你是否看懂了这个玩笑。尽管递归对初学者而言有点吓人，但实际上它很容易理解。一旦理解之后，你会发现它是一个优美的概念。

我认为解释递归的最佳示例是计算数字的阶乘：


我们可以轻松看出，阶乘就是一个递归函数。


那么如何将它迁移到编程呢？

递归调用函数通常包含两个部分：

  • 基线条件（base case）：递归停止的条件；

  • 递归条件：函数调用自己并逐渐向基线条件移动。


我们要解决的很多问题都是递归的，数据科学也是一样。

例如，决策树是二叉树，树算法通常是递归的。或者，我们经常使用 sort，负责 sort 的算法叫做 mergesort，是递归算法。另一个是二分搜索（binary search），涉及在数组中找到某个元素。

现在我们对递归有了基本了解，接下来我们来尝试找出第 n 个斐波那契数（Fibonacci Number）。斐波那契数列中的每个数字（斐波那契数）都是前面两个数字的和。最简单的示例是 1, 1, 2, 3, 5, 8, … 答案是：


你有没有发现其中的问题？

如果你尝试计算 fib(n=7)，函数运行 fib(5) 两次、fib(4) 三次、fib(3) 五次。随着 n 的值越来越大，同一个数字所需的调用次数越来越多，递归函数进行了一次又一次的计算。

破解数据科学面试，这里有最常考的三种算法


那么我们可以做得更好吗？当然。我们可以稍微更改实现，添加字典，从而为该方法添加一些存储过程。现在，每计算一次数字，该 memo 字典就会得到更新。当该数字再次出现时，我们无需再次计算，可以直接根据 memo 字典给出结果。添加存储叫做记忆（Memoization）。


通常，我喜欢先写递归函数，如果它多次调用同样的参数，我会添加字典来记忆解。

这有用吗？

破解数据科学面试，这里有最常考的三种算法

上图展示了 n 为不同值时，运行时间的对比情况。我们可以看到无记忆斐波那契数列的运行时间呈指数级增长，而记忆函数的运行时间则是线性的。

   动态规划

递归本质上是自上而下的方法。在计算斐波那契数 n 时，我们从 n 开始，对 n-2 和 n-1 执行递归调用……

而在动态规划中，我们采用自下而上的方法。它本质上是一种迭代地写递归的方式。我们首先计算 fib(0) 和 fib(1)，然后使用之前的结果生成新结果。


破解数据科学面试，这里有最常考的三种算法

上图对比了动态规划和记忆的运行时间。我们可以看到，二者均为线性，但是动态规划的速度要稍微快一些。

为什么？因为在该案例中，动态规划仅对每个子问题执行了一次调用。

   二分搜索

假设存在一个有序数组，我们想从中找出一个数字。我们可以按照线性方式逐个检查每个数字，直到找到目标数字。而问题在于，如果该数组包含数百万个元素，则这一过程会很长。这里我们可以使用二分搜索。

破解数据科学面试，这里有最常考的三种算法

找出数字 37。这片数字海洋里有 3.7 万亿条小鱼，而我们的目标是找出其中一条。（图源：http://mathwarehouse.com/programming）


还有一个基于递归算法的高级案例，该案例中我们利用有序数组这一事实。这里我们递归地查看中间元素，确认我们想要在中间元素的左侧还是右侧执行搜索。这就使得每一步的搜索空间减少了二分之一。

因而，该算法的运行时间是 O(logn)，而不是线性搜索的 O(n)。

这有多大作用呢？下图展示了二者的运行时间对比情况。我们可以看到二分搜索要比线性搜索快很多。

破解数据科学面试，这里有最常考的三种算法


   结论

本文介绍了构成编程基础的几个有趣算法。

这些算法隐藏在数据科学面试最常被问的问题背后，了解它们或许可以帮助你得到心仪的工作。

当然不学这些算法也不影响你在数据科学道路上的前进，不过你可以学着玩玩，或许可以提高编程技能呢。

原文链接：

https://towardsdatascience.com/three-programming-concepts-for-data-scientists-c264fc3b1de8


<pre style="max-width: 100%;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-right: 8px;margin-left: 8px;max-width: 100%;white-space: normal;color: rgb(0, 0, 0);font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;letter-spacing: 0.544px;text-align: center;widows: 1;line-height: 1.75em;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong>完<strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong></span></strong></span></strong></section><section style="max-width: 100%;white-space: normal;font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;letter-spacing: 0.544px;text-align: center;widows: 1;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-right: 8px;margin-bottom: 15px;margin-left: 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 25.5938px;letter-spacing: 3px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;font-size: 16px;font-family: 微软雅黑;caret-color: red;box-sizing: border-box !important;overflow-wrap: break-word !important;">为您推荐</span></strong></span></section><p style="margin-right: 8px;margin-bottom: 5px;margin-left: 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 1.75em;letter-spacing: 0px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">“12306”的架构到底有多牛逼？</span></p><p style="margin-right: 8px;margin-bottom: 5px;margin-left: 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 1.75em;letter-spacing: 0px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">中国程序员34岁生日当天在美国遭抢笔记本电脑，追击歹徒被拖行后身亡，为什么会发生此类事件？</span></p><p style="margin-right: 8px;margin-bottom: 5px;margin-left: 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 1.75em;letter-spacing: 0px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;-webkit-tap-highlight-color: rgba(0, 0, 0, 0);cursor: pointer;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;">阿里如何抗住90秒100亿？看这篇你就明白了！</span></p><p style="margin-right: 8px;margin-bottom: 5px;margin-left: 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;line-height: 1.75em;letter-spacing: 0px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(87, 107, 149);box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;">60个Chrome神器插件大收集：助你快速成为老司机，一键分析网站技术栈</span></span><br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"  /></p><p style="margin-right: 8px;margin-bottom: 5px;margin-left: 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 1.75em;letter-spacing: 0px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;-webkit-tap-highlight-color: rgba(0, 0, 0, 0);cursor: pointer;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;">深度学习必懂的13种概率分布</span></p></section></section></section></section></section></section></section></section>

本篇文章来源于: 深度学习这件小事

本文为原创文章，版权归所有，欢迎分享本文，转载请保留出处！

知行编程网
知行编程网 关注：1    粉丝：1
这个人很懒，什么都没写

你可能也喜欢

热评文章

上一篇
下一篇

发表评论

表情 格式 链接 私密 签到
扫一扫二维码分享
 繁