目录
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 吗?
- for i = 1 to n do
- if A[i] == t then
- Return TRUE
- Return FALSE
Algorithm 2 给定数组 A,B 和整数 t,A 或 B 中包含 t 吗?
- for i = 1 to n do
- if A[i] == t then
- Return TRUE
- for i = 1 to n do
- if B[i] == t then
- Return TRUE
- Return FALSE
Algorithm 3 数组 A,B 有相同的元素吗?
- for i = 1 to n do
- for j = 1 to n do
- if A[i] == B[j] then
- Return TRUE
- Return FALSE
Algorithm 4 数组 A 中有重复的元素吗?
- for i = 1 to n do
- for j = i+1 to n do
- if A[i] == A [j] then
- Return TRUE
- 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)中较大那个的两倍, 把两个不等式合在一起就是, 对每个, 都有确实位于两个不同倍数之间, 相当于今日互动
欢迎在评论区留下不懂的~
来源: https://www.cnblogs.com/siguamatrix/p/12771779.html