lec 17 Asymptotics I

CS61B

在看Lec17的视频时，Josh提了这么个问题：

我眼看着有两个for循环，二话不说选了C，结果：

这里说明我对big theta notation并没有理解，于是查了一些资料，看了一下群里朋友推荐的《算法导论》，但感觉全是数学上的解释，并没有很直观的解释；anyway, 在youtube上发现了一个视频讲得很清楚：
Asymptotic Notation

总结一下：

big O:

big Omega:

big theta:

这个视频是Havard跟Yale做的，只想说，超级牛校真的不一样，做的东西很清楚明了，一点也不装神弄鬼，语言非常平易近人，东西也讲得很直接简单，喜欢！ 不过要注意，在国外参加学术方面的会议，你只有很牛才能有资格轻视外表，普通人还是注意一下吧，不要学这个小哥穿凉鞋……

另外的资源：
What exactly does big Ө notation represent?

做了一下Asymptotics I的guide,错误蛮多，看来理解还不是很到位~

先看题目：

guide上面的定义里又讲到order of growth:

所以第一个肯定是对的；
第二个跟第一个是一样的；
第三个，既然all inputs 都满足，那worst case inputs肯定也满足；
第四个没毛病；
第五个false, 1000 may not be a large enough N to exhibit quadratic behavior。

答案：

题目：

第一题错了，O()是worst case，也就是upper bound, 最坏zengzhan是这样，可能也不是增长最快的情况是这样，可能完全没到upper bound还差很远这样；

第二题，还是那句话，big O means 增长速度不可能快过n2,所以这里说we will have to wait 100 times是不准确的，也完全可能不到.就算是worst case input, 也只能退出we will wait no longer than 100 times;

第三题，正确，几乎是Big o 的定义；

第四题第五题不是很清楚，简而言之不能仅根据big o 来推断big theta

答案：

A Level的那道题完全是在考对概念的理解，有几道题需要理解：

一些有用的资源：
what is the difference between Θ(n) and O(n)?
Difference between lower bound and tight bound?