【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 829|回复: 4
收起左侧

[其他] 数据结构算法学不进去 求打醒

[复制链接] |试试Instant~
我的人缘0
Kveikur 发表于 2018-7-13 02:46:36 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (9)
 
 
10% (1)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
lz这学期上了三门CS主干课(本科) 分别是函数式编程,形式语言与自动机,和数据结构与算法 前两门课都觉得很有意思也学得不错 然而对数据结构和算法课怎么都提不起兴趣 一打开课件看到一大堆各种xxxsort 各种O-notation 各种树 就觉得。。诶。。为什么要学这些 快排和归并那么好用 还管甚么选择插入冒泡 不看了!Order不就是求极限吗 不看了!。。平衡树居然可以高度差1 这还叫平衡树吗。。不看了!。。
之前一直听说这门课很重要很重要 是CS的核心课程 找工作也有用 但目前都没get到这门课的精髓是什么 总觉得 这门课无非就是在研究怎样加快计算的速度 然后便想 效率真的这么重要吗……
想听下前辈们对这门课程的意见。

上一篇:硕士AI专业,各个方向比较
下一篇:印度人现身说法 icc如何造假简历
我的人缘0
ztm 发表于 2018-8-4 02:32:44 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
这三门课从理论到应用的顺序是自动机、算法和函数式。自动机(计算理论)关注于这个问题能不能解决,而算法在研究怎么高效地解决问题,最后函数式(等编程课)告诉你怎么实现这个解决方案。
.本文原创自1point3acres论坛
你说的很对,算法在形式上确实都是“效率”。我不知道你的专业背景,但我只能告诉你,对于现在的任务来说,效率是至关重要的,因为这是工科。当n不太小(比如大于40)时,不同复杂度的算法的效率差异非常明显。这是这门学科的必要性。. 牛人云集,一亩三分地

. 1point 3acres 论坛具体来说,排序算法之间的比较可以很好地刻画这个学科的特性,比如:
当n很小时,冒泡排序反而比快速排序快 ==> 运行时间和常数有关,你可以看看C++ STL中的sort(或者是qsort?)是怎么实现的,还有众多大整数乘法的算法;
当我们知道逆序对中的两个元素的距离大概率不远(<k)时,选择排序的复杂度为O(nk),当k为常数时是O(n)的 ==> 当我们知道更多信息时,我们关注的其实是个很特殊的子问题,此时很可能存在特殊的算法更加高效;
当数组元素都不大时,可以使用桶排序,你可以思考一下桶排序的时间复杂度为什么这么优秀(对比Turing machine和现在的计算机结构) ==> 可以利用硬件的特性来设计更优秀的算法;
快速排序介绍了很重要的思想:随机化,即大概率会有优秀的效率;
快速排序、归并排序等可以并行化,但堆排序不可以,而并行化在当下显然是十分重要的(另一方面,堆是数据结构,可以处理多种操作,有很多trick,而且被非常广泛地使用);
当数组非常大以至于main memory存不下而只能存放在IO非常慢的disk里,快排和原版的归并都很慢,我们可以使用归并和heap sort的结合来提速(external sorting) ==> 算法的设计和选择受硬件限制。

我不清楚你学了多少数据结构(树)。这些一般处理有时序的操作,同时维护内在“秩序”。操作有很多种,比如对单点操作和对连续序列操作,甚至更复杂的。举例来说,平衡树维护了有序序列,还可以高效地知道前缀和等等。在这里,“平衡”,和快排很类似,指的是分治思想中“平均地分”的概念,只要大概率地比较平均即可。. 一亩-三分-地,独家发布
数据结构可以高效地“记录”这些操作:事实上它并没有实现这些操作,但是它可以高效地知道这些操作所带来的结果,比如线段树。
当这些操作出现的频率已知时,我们可以选择不同的数据结构来对不同操作的时间复杂度进行取舍,比如斐波那契堆。
有时内在秩序很复杂而且操作也很复杂,我们往往需要更复杂的数据结构,比如动态树。
在处理一系列操作时,可以有离线和在线做法,这在一般情况下可以相互转化。
如果我们不要求每个操作的response time都很小而要求average response time很小,我们可以使用均摊的思想(你可以看看动态树的证明,只有伸展树Splay可以用)。
. From 1point 3acres bbs
在算法设计和复杂度的证明中,也有很多很重要的思想,比如均摊、分治、随机化。

当然,提高效率也有很多别的方法,比如用GPU、用并行,比如常数优化(树状数组、位运算)。而且很多算法很琐碎,并没有很深的思想,但是它解决了十分常见的问题,从工科的观点来看。

对于绝大多数人来说,在工作中绝不需要亲自写这些算法和数据结构,因为别人已经写好了。但是你在formalize问题的时候,需要知道如何利用这些算法提高效率,比如AOV和动态规划。更进一步地,当计算理论证明了问题不可解时,你可能需要找到高效的近似算法。换言之,你需要知道它们怎么工作、为什么工作,也需要知道背后的思想。
. 1point 3acres 论坛
我学的并不多,没有看过前沿研究,目前也不打算从事相关研究,只作为学习者来聊聊自己的看法。而且我很久没有接触算法和数据结构了,仅凭印象写了这些东西,难免有疏漏。
资历最老的留学申请文书修改服务:EssayEdge
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
小时候可帅哝 发表于 2018-7-13 04:53:51 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  91% (79)
 
 
8% (7)  踩
上这些课的意义并不是说让你写的每一段代码都能优化到最好, 而是你能清楚得知道你写的代码在什么样的效率运行.
我觉得这是作为码农最基本的意识了.
. 留学申请论坛-一亩三分地
O(n), O(logn), O(n^2) and O(n^n). 你随便写点东西, 一旦把n放大到百万, 千万级, 这几个的效率能差别多大.

回到现实来说,
你刷知乎, 每翻一页卡一下, 你能接受么?
你上PxxnHub, 看视频10分钟就全屏马赛克, 你能接受么?
你上B站, 刷新一下, 3分钟的视频, 重新load弹幕要5分钟, 你能接受么?

反正我是不能接受.   这样描述可能过分简化, 但是, 行和不行大概就是O(logn)和O(n^2)的区别. .1point3acres网
那你说, 性能重要不..   我觉得, 对于自己的代码的性能在心里有点AC数是码农的基础修养.



评分

参与人数 1大米 +40 收起 理由
rexue70 + 40 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘3
pxu 发表于 2018-7-13 04:31:13 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  67% (307)
 
 
32% (149)  踩
关键是你毕业后要找什么工作。如果做程序方面的,特别是大公司,人家就是要考那些东西呀(还不完全只是死考数据结构算法的概念)。你不去把怎么东西搞得,相信会吃些苦头。如果你是富二代的话,无所谓啦,混混都可以。如果在国外的话,以后就回国继承家业,比俺们苦苦奋斗的人,不知道幸福多多哟。
回复

使用道具 举报

我的人缘0
Anakin09 发表于 2018-8-5 09:51:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  78% (206)
 
 
21% (56)  踩
lz大几啊,等到要找实习的时候刷刷leetcode,数据结构算法还不是学的美滋滋
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-26 00:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表