新南威尔士大学 · University of New South Wales

文 | Sunny

编辑 | Sunny

拥有这一份完美笔记

定能够让你在盗墓，打怪的同时

也能够

震撼经验住全场！

 

Week 3：Analysis of Algorithms 

准备好接招吧，上周的知识点总结福利发送啦

>运行时Running Time

a. 一般指的是worse case running time

b. 理论分析，无需代码实现

c. 与操作系统、软硬件无关

 

>学会读/写Pseudocode

考点1：  能够通过分析pseudocode，计算Primitive Operations的数量

考点2：  能够通过分析pseudocode，估计running time

>O(…)

考点1： 定义：已知函数f(n)和g(n)，如果存在两个正数常量c 和 n0 ，对于任意的值n ≥ n0，都有f(n) ≤ cg(n)，那么我们就认为f(n) = O(g(n))。

考点2： f(n)的增长率不会超过 g(n)，其实O(…) 就是增长率的上界

考点3： 根据定义计算c 和 n0 两个值

考点4： f(n)是d次多项式时，如何运用O(n)规则

 

>计算Prefix Averages

考点1：  定义：A[i] = (X[0] + X[1] + … + X[i])/(i+1)

考点2：  通过计算Prefix Averages，得到Running time

 

>Binary Search

 考点1： 掌握递归算法的pesudocode:   注意--计算mid值 + 递归搜索的范围

考点2：  注意时间复杂度：O(logn)

 

>递归算法的空间复杂度分析

考点1： 主要是考虑stack空间(存放局部变量，返回地址等)的分析

考点2：  掌握如何计算方法调用所需堆栈空间的最大值?

• 步骤一：绘制调用图

• 步骤二：在调用图中找出最长的加权路径

>O(…), Ω(…) 和Θ(…)的区别

注意哦：

• O是一个算法最坏情况的度量 – upper bound

• Big Omega是最好情况的度量 – lower bound

• Big Theta表达了一个算法的区间 – avg case

小本本有木有记下来啊?

学习到这里，如果还不明白的话

没有关系！

扫码入群

更有定期免费资料福利发送哦！

为什么要选择匠人的辅导课程？

匠人臻选多门课HD大神（成绩90%+）做tutor，同时又有专业职场老司机做顾问，无论问题深或浅，都有大神相助                                                        

任职tutor了解你的课程考试作业与项目全部，都是该课以及相关课7分大神    

匠人多种优惠活动帮你节约成本，同时也为学习好的同学提供舞台                 

可以根据学生情况灵活制定课程内容与时间

Tutor服务方式

我们为同学们提供多种形式的服务，IT匠人会提供如下服务：

VIP定制课程1对1辅导，护航冲刺班，作业辅导班，作业审查服务，考试冲刺班

这些语言涵盖了大学IT/CS专业的课程，由于大学课程要一一列出来会太多，所以有需要的小伙伴可以联系我们的客服。

常见问题

是不是还是有点没看懂啊，让我们来看看小伙伴们会有的常见问题。

Q:一对一上课是干些什么？

A:根据学生需求，老师提供相应的帮助。换言之只要不代写聊作业，聊学习，聊人生聊理想，聊什么都可以。

Q:可以可以便宜一点？

A:20小时以下：转发朋友圈减$10，20小时以上：分享到微信朋友圈（或100人以上新生群）截图优惠$50

Q:一对多的上课内容有是什么？

A:一对多和一对一非常的相似，但是价格更实惠且同学之间可以互相讨论。总之老师会根据学生们的要求，进行授课。

Q:如果对老师不满意怎么办？

A:有任何关于tutor的不满的地方马上联系客服换人，且每次补课结束都有学生反馈的表格可以填写，如果不满意请如实填写在反馈表上，工作人员贵根据反馈进行跟进调查。

Q:作业辅导和作业审察有什么区别？

A:作业辅导只是对学科lecture知识点和tutorial作业进行讲解，而不会对学生的作业进行检查纠错和订正。而作业审查恰恰相反。

Q：护航班会干啥？

A: 每周三小时的课主要分为1h 本周知识点讲解45 mins，Tutorial讲解45 mins Assignment 讲解10 mins 答疑20 mins 以及预习下周的知识点。

Q:护航班一定要上为什么这么贵

A:因为护航班每周三小时用中文来帮助学生消化一周所学知识。对于基础薄弱的同学，有些科目学起来会力不从心，而上护航班可以有效帮助他们更高效的理解所学内容避免挂科。

Q:考试冲刺班要干些啥

A:解答历年的试题类型考题，考试经验分享与技巧分享整理知识点回顾。

Q:如果我对IT不了解怎么办？

A:那您可以去护航班，因为护航班的老师会对你进行知识点的落实和作业上的指导。

 

* IT匠人圈已经有7个满的求职技术交流群，每个城市的匠人群，各大学的IT/CS新生群，行业交流群（大前端，Devops，Mobile，数据等等）