前段时间，Github 推出了 copilot，一石激起千层浪，引起纷纷热议，也得到很多批评，说它只是 Google 和 StackOverflow 的搬运工而已。
​

而我，竟然有幸收到了 Github 在 7 月 11 日发来的内测邀请，于是决定好好体验一番，毕竟面向 Google 和 StackOverflow 编程的我，对于 copilot 是不是抄袭 Google 和 StackOverflow 上的内容，还是能明显感觉出来的。
​

image.png

实测结果

​

体验了一个多月下来，线上结论，太惊艳了！绝对不只是搬运工，反正我已经退化成一个只会按 Tab 键的工具人了，因为它总是给我正确的建议，只需要按下 Tab 键，就能完成我想完成的工作。
​

编程体验

​

写代码的体验，其实网上的分享已经很多了，我不多做赘述，只分享一件小事。月初面试一名候选者，我本来让他在白板上写代码，但是他很有想法，反问我为什么不让他在电脑上写代码，于是等他在白板上写完代码后，我又加了一道题，让他在我电脑上写，我帮他开了我的 vscode。
​

他写了没几行，就惊呼：你用了什么插件？它怎么知道我要写什么！
​

写作体验


编程体验不多说，本文想着重分享一下写作体验。是的，copilot 不仅在编码上体验出色，而且还能帮助你写文章，甚至能够“理解”上下文，做一些逻辑推理，并猜出你接下来想写什么！
​

其实接下来才是本文的重点，来点截图看看 copilot 在写文章时的表现吧！
​

根据上下文猜出你接下来想些什么

image.png
image.png
image.png

提供多个选项

​

image.png

可以理解你写的文字，并做出逻辑推理

​

image.png

image.png

最惊艳的表现！完全理解我敲入的内容，并猜出我想说什么，而且总结得完全正确！


image.png
image.png
image.png

image.png

image.png

image.png

我和 copilot 合作写的文章全文


以上就是我在写文章时，使用 Copilot 的体验，整个过程我没有打多少字，几乎就是按一按 Tab 键。对于 Tab 键后的内容，我几乎没有修改过。如果说修改，也是修改自己的仅有的一些措辞，然后接受新的建议。
​

以上全是 copilot 的广告，最后才是本文的真正内容部分，《增长的秩》。这是我在阅读《SICP》时碰到的问题，就是居然在算法复杂度分析时完全没有提到大 O 标记法，这是为什么呢？请看全文：
​

​

​

​

​

增长的秩

增长的秩，即增长的数量级，是对算法复杂度的度量。一般程序员熟悉的大 O 标记法，就是增长的秩的一种表示方法。
​

但是本书居然没有提及这种标记方法，而是采用了大 Θ 标记法。程序员们不禁要问，这两种标记法有什么区别？
​

先上结论：大 Θ 标记法提供的信息更多。
​

SICP 通过很多例子展示了不同算法的处理过程在消耗计算资源的速率上的巨大差异。它说要描述这种差异，有个简单的办法，就是使用增长的秩，来大致估计当输入变得更大时所需要的计算资源。精确定义如下：
​

使用 n 这个参数来描述问题的规模，用 R(n) 来表示处理过程为处理这个规模为 n 的这个问题所需要的资源的数量。对于指定的待分析的处理过程，其所处理的问题有很多个属性可以用作这个参数 n。比如要计算平方根的近似值，可以采用精确的小数位数作为 n；对于矩阵乘法，可以采用矩阵的行数作为参数 n 等等。类似地，R(n) 既可能是被使用到的存储寄存器的数量，也可能是执行的基本机器操作次数，等等。计算机在指定时间只会执行有限次数的操作，所以一个处理过程所需要的时间是和其执行的基本机器操作的次数成正比的。
​

大 Θ 标记法


当我们说 R(n) 具有 Θ(f(n)) 的增长秩时，记作 R(n) = Θ(f(n))，这就意味着存在两个独立于 n 的正常数 k1 和 k2，它们对所有足够大的 n 满足如下关系：
​

k1 f (n) ≤ R(n) ≤ k2 f (n)
​

即，当 n 足够大时，R(n) 的值被夹逼在 k1 f(n) 和 k2 f(n) 之间，像个三明治一样。
​

以上对于大 Θ 标记的定义做了详细的介绍，现在我们知道它提供了一个函数的上下极限这两个信息，而大 O 标记提供的信息更少，就是因为它只提供了上极限。
​

大 O 标记法

​

当我们只有一个上限渐进值时，我们一般采用大 O 标记法，精确定义如下：
​

对给定的函数 g(n)，O(g(n)) 是这样的函数的集合：
​

O(g(n)) = {f(n) : 存在正常数 k 和 n0，对所有大于等于 n0 的 n 都满足 0 ≤ f(n) ≤ k g(n)}。
​

它们的关系

  • 所有的大 Θ 标记法都是大 O 标记法的子集。但反之不成立。
  • T(n) 等价于 Θ(f(n))，如果它既是 O(f(n)) 的，又是 Ω(f(n)) 的话。

​

大 Θ 标记法比大 O 标记法提供的信息更多，所以只要可能，使用大 Θ 标记法将是更受推荐的，这也是为什么 SICP 这本书只使用了这个标记法的原因。
​

但是，使用大 Θ 标记法会更加困难，因为要证明大 O 成立会比证明大 Θ 成立更加简单。
​

比如，归并排序既是 O(n log n) 的，又是 Θ(n log n) 的，但同时还可以是 O(n2) 的，因为 n2 是更“大”的值。但是它不可能是 Θ(n2)，因为这个算法并不是 Ω(n2) 的。（这个来自某大佬的说明，我还没有理解…… 也许是这个大佬说错了，还有待进一步思考和学习）

大 Ω 标记法


理解了上述大 Θ 标记法和大 O 标记法后，理解大 Ω 标记法就很容易了。它给出了函数的下逼近值。
​

即如果 T(n) 是 Ω(f(n)) 的，那么存在一个数 n0 和 k，使得 T(n) ≥ k f(n) 对于所有 n ≥ n0 成立。
​

总结


对于增长的秩（算法复杂度），有三种标记法，分别是大 Θ 标记法、大 O 标记法和大 Ω 标记法。他们都只给出了当输入很大时近似值。
​

  • 大 Θ 标记法：给出了函数的上极限和下极限。
  • 大 O 标记法：给出了函数的上极限。
  • 大 Ω 标记法：给出了函数的下极限。

​

要注意的是，这三种标记法和算法复杂度分析中的最好、最坏以及平均情况是不同的，它们都可以用在每一种情况的分析中。