Open topic2: 大O（ Θ ，Ω）和小o（ θ ，ω）有什么区别？ 3/19/18 黄秉焜

Presentation on theme: "Open topic2: 大O（ Θ ，Ω）和小o（ θ ，ω）有什么区别？ 3/19/18 黄秉焜"— Presentation transcript:

1 Open topic2: 大O（ Θ ，Ω）和小o（ θ ，ω）有什么区别？ 3/19/18 黄秉焜
大家其实之前应该都接触过用渐进符号表示时间和空间复杂度的方式，比较多的应该是大O，或者说大omicorn 这些渐近符号都是有严格定义的，如果大家已经在作业中有一些了解，那么应该会自然地和我们见得比较多的符号联系在一起，比如说，大于，小于，小于等于 今天的open topic是要比较他们之间的区别，但在我看来，只要对他们的定义足够清晰，那么区别自然就出来了 所以我打算先再一次介绍、定义这些符号，我觉得从这些直觉的东西引入并不是一件坏事 我们来看一下这几句话 3/19/18 黄秉焜

2 在这里，a 指的就是f(n), b 指的就是g(n)
先记住这些，我们再来看第一， 先说说这5个中条件最强的一个符号，大theta

3 asymptotically tight bound 渐近紧确界
集合里冒号的意思就是使得 对于任意一个大于n0的n，都有f(n)在这两个函数之间 另外定义里面要注意一下这个大于等于0，老师之前上课的时候提到过，问到过大O(n)里面是否包含（-n）类似的话，这在算法分析里面并没有什么实际意义 我们会很自然地联想到夹逼，再想想之前那几句话，大theta像等于，这应该好理解 而满足这样的关系，g(n)就叫做f(n)的渐近紧确界 现在回到实际的算法分析中，如果我们说一个算法的时间复杂度是theta(n^2)，那我们的意思就是说这个算法在n的规模足够大的情况下，不管是最好情况还是最坏情况，它都在c1n^2和c2n^2之中。 这里顺便抛个疑问，如果这个算法的time cost恰好就只有一项二次项，那么这当然没问题，但往往并非如此

4 鉴于此，我们可以容忍我们的某种程度上的“粗心”
我们往往忽略不同语句的执行开销差异并标准化 C1=C2=…=C8 这是上节课的一张ppt，我们最终认为，这个算法的时间复杂度就是n^2，这种“粗心”到底是不是对的呢？ 这个证明是很显然，n规模很大的时候，后面的项就忽略不计了，其他的logn也可以很容易证明出来 T(n) = 1.5n2+3.5n-4 ~ 1.5n2 ~ n2

5 有了大theta的定义，我们很容易就能理解大O和大omega,他们相较于大theta,不过是一个少了下界，一个少了上界，大家可以看这三张图比较一下，n0之后就都满足定义了

6 大O（ Θ ，Ω）和小o（ θ ，ω）有什么区别？
那我们现在进入正题，比较大小渐近符号的不同 还是回顾一下这张图， 可能放太大了不太清楚，下面两个是小o和小omega OK，我知道有些同学已经知道他们的区别是什么了， 现在我们这么看

7 大O（ Θ ，Ω）和小o（ θ ，ω）有什么区别？
集合 这些符号代表着什么？ 他们代表的是集合

8 我们再次回顾这三个渐近符号的定义 没错，他们就是这样一些符合条件的f(n)的集合 我用文字，图像，极限公式来帮助大家再加深一下印象 虽然我还没讲小o和小omega的定义，但请看这个

9 ？ 这两个并集运算结果是什么？ 大家都知道，是大O和大Omega，虽然我还没给出小o和小omega的定义，但今天open topic 的问题应该解决了 小o是大O的真子集，theta是小o相对于大O缺的那一部分，Omega同理

10 严格的定义就是这样 当然大家可能已经发现了，我好像只做了两组对比，小theta和大theta的对比好像没有 实际上是因为我找到这方面的资料时，完全没有发现小theta在算法分析中的出现

11 Wiki上对theta的解释，小theta没有
倒是隔壁班一位同学发现了这个选题后面的坑，顺便把我拉出来了

12 个人觉得，老师应该是要让我们讲大theta和这个tilde符号的区别
实际上呢，tilde应该是一个比大theta条件更强的符号 Theta是一种同阶的关系，它只要求，在经过两个常数的修正之后，f(n)会被g(n)夹住，而tilde就接近于相等了，在没有常数系数修正的情况下，f(n)和g(n)在无穷远处的比值为1，因为tilde几乎不在算法分析中出现，所以我也不细讲了，这张表格还有一栏被遮住了，感兴趣的同学可以下载PPT回去看一下 另外说到这个大theta,还有一点要注意，就是大theta条件更强，如果用它来表示算法复杂度，那要更准确一点，但有些情况要注意，比如说

13 你能用Θ来表示它们的running time吗？
平时我们用大O比较多，可能是大O写起来方便，可能是大多数情况下，我们关注算法的最坏情况，当然是大家分不清大theta和大O。也可能是这种，我们虽然可能强调其中一种情况，比如worst case,但我们也想包含best case和 average case的情况。 比如我们可能就会说这个算法的时间复杂度是O（n^2) 现在我想再一次回到开头的那个比喻

14 The table is sorted from smallest to largest, in the sense that o, O, Θ, ∼, both versions of Ω, ω on functions correspond to <, ≤, ≈, =, ≥, > on the real line. 之前给大家看的那5个比喻实际上是算法导论里面的，在找资料的过程中，还发现了，wiki上，知乎上，博客上，一篇追溯渐近符号历史的文章上，都提到过这些比喻，这些比喻可以说是很恰当的，这种恰当，实际上源于他们共同的性质

15 从集合关系的角度来讲，他们的性质和相对应的大于小于这些符号是一样的，所以能很自然地作出这些比喻。
转置对称 那么最后随便讲讲吧 当然实际上我们用这些符号经常是不太严格的 不是有这么一件事吗，一个数学家看到物理学家的解题过程，很生气地说，你怎么能这么胡乱运算呢，这都不是一致连续的。物理学家一摊手，说，那我不管，反正我做出来了。 仔细想想，我们也确实不算严格的数学家。 谢谢大家