【斯坦福算法分析和设计02】渐进分析

目录

• 1. The Gist
• 1.1 为什么要学它(Motivation)
• 1.2 High level idea
• 1.3 4个例子
• 2. Big-Oh Notation
• 2.1 文本定义
• 2.2 图形定义
• 2.3 数学定义
• 3. 2个例子
• 3.1 k阶多项式是O(n^k)
• 3.2 k阶多项式不是O(n^(k-1))
• 4. Big Omega and Theta
• 4.1 Big-Omega表示法
• 4.2 Big-theta表示法
• 4.3 Little-O表示法
• 4.4 渐进性表示法的来源
• 5. 几个额外的例子【可选】
• 5.1 在指数中添加一个常数
• 5.2 指数乘以一个常数
• 5.2 最大值和求和

1. The Gist

1.1 为什么要学它(Motivation)

我们的目的是寻找一种对算法进行衡量的最有效力度，我们希望忽略不重要的细节，例如常数因子和低阶项，把注意力集中在算法的运行时间是怎样随着输入长度的增长而增长的，这些任务是通过大O表示法(包括它的近亲表示法)的形式完成的，每个 程序员 都应该掌握这个概念。

它是行业术语渐进性表示法提供了讨论算法设计与分析的基本术语，当我们听到某个程序员谈论他的某段代码以"n的大O时间运行"，而另一段代码，以"n平方的大O时间运行"时，我们需要知道其中的意思。它是区别不同算法的"sweet spot"它有粗放和精细的两个特征。粗放:忽略了所以我们想要忽略的细节，比如说计算机体系结构，具体选择的编程语言以及编译器等方面的细节。精细:可以在不同层次对解决这个问题不同算法进行比较，尤其在巨大输入情况下，输入的规模越大，就越需要精妙的算法。

1.2 High level idea

一句话概括渐进性表示法的话，就是忽略常数因子和它的低阶项。

为什么我们要忽略常数因子和它的低阶项？根据定义，我们把注意力放在大规模的输入时低阶项的作用就几乎可以忽略了，而大规模的输入才是需要精妙算法的时候，同时常数因子一般高度依赖于环境的细节，如果我们分析算法时并不想固定于某种特定语言计算机体系结构和编译器，那么使用不在意的常数因子就会非常合理。不是说忽略的就不重要，什么时候它重要？忽略的意思并不是说常数因子是完全无关紧要的，只不过当我们想要对解决同一个问题的一些不同方法进行比较的时候，渐进性表示法往往是正确的工具，它能帮助我们理解哪种算法的性能最佳，尤其是当输入规模非常大时，但我们确定了某个问题的最佳高级算法后，可能还想进一步优化常数因子和低阶项。

1.3 4个例子

这里有4个比较简单的例子，如果是第一次接触这个概念的朋友可以自己试着做一下，求每个例子的渐进性运行时间。后台回复【渐进性表示法】查看答案。Algorithm 1数组A中包含整数t吗？

1: for i = 1 to n do  
2:   if A[i] == t then  
3:       Return TRUE  
4: Return FALSE

Algorithm 2给定数组A，B和整数t，A或B中包含t吗？

1:  for i = 1 to n do
2:     if A[i] == t then
3:         Return TRUE
4:  for i = 1 to n do
5:     if B[i] == t then
6:         Return TRUE
7:  Return FALSE

Algorithm 3数组A，B有相同的元素吗？

1: for i = 1 to n do
2:    for j = 1 to n do
3:       if A[i] == B[j] then
4:           Return TRUE
5: Return FALSE

1: for i = 1 to n do
2:    for j = i+1 to n do
3:       if A[i] == A [j] then
4:           Return TRUE
5: Return FALSE

2. Big-Oh Notation

2.1 文本定义

大O表示法关注的是定义在正整数n = 1,2,3..上的函数T(n)，T(n)总是表示某个算法的最坏情况运行时间的上界，那么当我们说T(n)=O(f(n))的时候表示什么意思呢？

T(n)=O(f(n))当且仅当T(n)的最终上界是f(n)的一个常数积。

2.2 图形定义

由下图我们看到T(n)的上界并不是由f(n)决定的，是由f(n)乘以3所形成的上面那个虚线决定的，当n的值足够大时超过n0这个分界点，之后它的值就会大于T(n)，所以T(n)实际上最终是由f(n)的常数积确定上界，我们就可以说T(n)=O(f(n))。

这里的常数c满足f(n)的常数倍，常数n0满足最终。

2.3 数学定义

T(n)=O(f(n))表示当且仅当存在正常数c和n0，对所有的，不等式都成立。这个数学公式实际上是对文本定义的直接翻译。“对所有的n大于等于n0”表示这个不等式只需要当n足够大的时候(n0确定了具体的大小)最终能够成立，而在图中常数c对应的是3，n0对应的是函数T(n)和cf(n)之间的分界值.warning:一个警告，当我们说c和n0是常数，意思是它并不依赖于n，比如说图中的c和n0是固定的数字，像是300，1000，如果我们在证明中看到n0=n，或者c=log(n)这样的说法，它就是与n有关的，就不是常数值了。

3. 2个例子

3.1 k阶多项式是O(n^k)

这个命题表示在多项式的大O表示法中，我们需要关注的是出现在多项式的最高阶。因此大O表示法确实忽略了常数因子和低阶项。简化版的证明过程如下

以下是详细版本的解释。根据大O表示法的数学定义，我们需要的是找到一对正整数c和n0，我们先假设这两个常量的值: n0=1,c等于所有系数的绝对值之和：。这两个数都与n无关，现在我们需要证明选择的这两个常量满足不等式，即对所有，都有。首先我们看看T(n)的定义:如果我们在右边取每个系数的绝对值，这个表达式只会变得更大。(只会比更大，由于是正数，只会比更大)，于是:既然系数是非负数，我们也可以用类似的技巧让n的不同乘方转换成n的公共乘方。由于，对于每个，只会比更大，由于是非负正数，所以只会比更大。就意味着:对于每个，这个不等式是成立的，这就是我们想要的证明结果。

3.2 k阶多项式不是O(n^k-1)

它表示不同阶的多项式的大O表示法是不同的。我们可以用反证法，假设结论的相反结论是对的，并在这个假设上进行一系列的逻辑正确的步骤，最后推导出出错。简单的证明过程如下

以下是详细的文字解释。因此假设=，那么它意味着什么呢？的最终上界是的一个常数积确定的。也就是说，存在常数c和，对于所有的，都存在由于n是正数，我们可以从两边消去，于是对于所有的，都存在。相当于说c比每个正整数都要大，这是明显错误的（可以取n的值是c+1向上取最接近的整数），这就说明原来的假设是错误的。

4. Big Omega and Theta

4.1 Big-Omega表示法

文字表示法就是，当且仅当T(n)的下界是由f(n)的一个常数积所确定，那么T(n)就是另一个函数f(n)的大。数学定义如下:

当且仅当存在正常数c和，使得对于每一个，都有。对应的图形式如下:

f(n)并没有确定T(n)的下界，但是如果把它乘以常数，那么就是在临界点的右边确定了T(n)的下界。

4.2 Big-theta表示法

它可以类比于“等于”，相当于同时满足和，相当于T(n)被夹在f(n)的两个不同的常数积之间。数学定义如下:

当且仅当存在正常数，使得当的时候，有。

4.3 Little-O表示法

T(n)=o(f(n))表示当且仅当对所有c>0的常数，存在常数n0，对所有的，不等式都成立。

4.4 渐进性表示法的来源

渐进表示法不是由计算机科学家发明的，是开始于数论。

5. 几个额外的例子【可选】

5.1 在指数中添加一个常数

这个例子是说，一个函数的指数与一个常数相加，并不会改变这个函数的渐进性时间增长率。简化的证明过程:

更详细的解释:要证明这个，我们需要找到合适的正常数c和，使得对于所有的，T(n)的最大值是，我们来对它进行反向工程。

我们在寻找一个推导方式，不断的放大T(n)使得它是的常数倍，我们看到T(n)的指数里有个10，很自然的想着把它分出去:我们发现右边就是的常数倍，这就提醒我们c取1024。假设选择这个c，那么对于所有的都有，因此我们取，那么就证明出来了。

5.2 指数乘以一个常数

这个命题的意思是，把一个指数函数的指数和一个常数相乘改变了它的渐进性增长率。简化的证明过程:

更详细的文字:这个用反证法来证明，它的相反结论是对的，就是。根据大O的定义，存在正常数c和，对于所有的，都有，因为是个正数，所以我们可以两边去掉，就得，这个是错误的，因为右边是个固定的数，而左边是随着n增加而无限增加的，说明我们的假设是错误的，这就证明得了原问题。

5.2 最大值和求和

这个例子表示从渐进性的角度，取两个非负数的逐点最大值和取她们的和没有什么差别。简化的证明过程:

的含义表示T(n)最终位于f(n)的两个不同常数倍之间。我们需要三个常数:，，，后面两个对应较大倍数和较小倍数。我们对几个数进行反向工程。任何一个正整数都存在以下关系:因为不等式的右边就是左边的数加上另一个非负数(f(n)和g(n)中较小的那个数)。类似的因为不等式的左边是f(n)和g(n)中较大那个的两倍，把两个不等式合在一起就是，对每个，都有确实位于两个不同倍数之间，相当于今日互动

欢迎在评论区留下不懂的~