对大O记号两个性质的证明

作者: Leesper | 来源:发表于2022-08-01 00:16 被阅读0次

要认真理解基本概念，复杂问题无非就是简单问题的约束性组合。

——刘杨

在对计算机算法进行渐进时间复杂度分析时，针对足够大的输入规模n，算法执行时间T(n)的渐进增长速度，有一个渐进上界的估计，用大O记法表示。

若存在正的常数c和函数f(n)，使得对任何 $n \gg 2$ 都有 $T(n) \leq c \cdot f(n)$ ，则可认为在n足够大之后，f(n)给出了T(n)增长速度的一个渐进上界。此时记之为：

$T(n) = O(f(n))$

由这一定义，可以导出大O记号的以下性质：

（1）对于任一常数c > 0，有 $O(f(n)) = O(c \cdot f(n))$

（2）对于任意常数a > b > 0，有 $O(n^a + n^b) = O(n^a)$

最近不是在看匈牙利数学家波利亚写的《怎样解题》嘛，我就突发奇想：如果让我来证明这两个性质，应该不难吧？我该如何证明呢？

题目的已知数据，是正常数c和一个在非负整数域上的函数f(n)，n为问题的规模，f(n)为算法执行的最长时间，所以f(n)的值域也是非负的。未知量是要证明的两个结论。

观察结论，未知量和已知数据之间通过大O记法联系在了一起。突破口很可能就在大O记法本身的定义上，于是，我们先回到定义上去，认真研究一下上面对大O记法的定义。

仔细理解这个定义，它想表达什么意思呢？当n足够大的时候，从函数图像上来看，f(n)就像是T(n)上方的一个无法逾越的鸿沟，T(n)的取值永远都小于等于f(n)乘以一个常数的值。但它对证明这两个结论有什么帮助呢？看上去似乎没有，要证明的结论两端都有大O记法，好像并不能直接应用 $T(n) = O(f(n))$ 来做点什么推导。

$O(f(n)) = O(c \cdot f(n))$ 中的等号是什么意思？ $T(n) = O(f(n))$ 中的等号又是什么意思？它们是一个意思吗？仔细想想并不是的。 $T(n) = O(f(n))$ 中的等号，隐含的其实是小于等于，是 $T(n) \leq c \cdot f(n)$ 的意思。也就是说存在一个T(n)，当n足够大时 $T(n) \leq c \cdot f(n)$ 。那么我可能找到很多个函数都满足这个不等式， $O(f(n))$ 是啥？对了！它本质上是一个集合，集合中的每个元素T都是一个函数，都满足 $T(n) \leq c \cdot f(n)$ 。所以两个性质中要证明的结论其实是想证明两个集合相等。也就是说，在深刻的理解了定义，并搞清楚大O记法的本质后，我们以一种不同的形式重新叙述了要证明的结论：其实就是证明两个集合相等。

$\forall e \in A，e \in A \to e \in B$ 且 $\forall e \in B，e \in B \to e \in A$ ，那么A = B。这就是证明两个集合相等的方法。另外，从大O记法的定义中，我们能读出一点熟悉的味道，就是微积分中“极限”的概念：
$\lim_{n \to \infty}\frac{T(n)}{f(n)} = c$
可以给出（1）的证明了：
$\forall T(n) \in O(f(n))，有：\\ \lim_{n \to \infty}\frac{T(n)}{f(n)} = c，\\ 根据极限性质，两边乘以1/c，得到\lim_{n \to \infty}\frac{T(n)}{cf(n)} = 1，\\ 再由大O记法定义，可知T(n) = O(c \cdot f(n))，得到O(f(n)) \subseteq O(c \cdot f(n)) \\ \forall T(n) \in O(c \cdot f(n))，有：\\ \lim_{n \to \infty}\frac{T(n)}{c \cdot f(n)} = c'\\ 两边同时乘以c，得到\lim_{n \to \infty}\frac{T(n)}{f(n)} = c \cdot c' = c'' \\ 由大O记法定义，可知T(n) \in O(f(n))，故O(c \cdot f(n)) \subseteq O(f(n)) \\ 综上可得：O(f(n)) = O(c \cdot f(n))$
再给出（2）的证明：
$T(n) = O(n^a + n^b) \Leftrightarrow \lim_{n \to \infty}\frac{T(n)}{n^a + n^b} = c，c > 0 \\ 因为a > b > 0，\lim_{n \to \infty}\frac{n^a + n^b}{n^a} = \lim_{n \to \infty}(1+\frac{1}{n^{a-b}}) = 1 \\ \lim_{n \to \infty}[\frac{T(n)}{n^a + n^b} \cdot \frac{n^a + n^b}{n^a}] = \lim_{n \to \infty}\frac{T(n)}{n^a} = c，所以T(n) = O(n^a)$
总结一下，在真正理解大O记法深刻含义（集合）的基础上，我们从观察结论出发，找到了正确证明这两个性质的思路，即证明两个集合相等。证明两个集合相等的方法以前在别的题目中是做过的，可以直接拿过来用。再从大O记法的定义出发，成功解读出它的“极限”的含义，从而和微积分中学过的函数的极限联系起来，然后通过极限的性质，成功地对这两个性质进行了证明。已知数据和未知量之间联系的条件，是集合相等，以及函数极限的性质。

反思一下，解决问题的时候要找思路，而不是遇到一点困难就开始自我攻击。一直以来我有个思维方式的怪圈：尝试解决问题--->思考半天没有思路--->忍不住看答案--->开始懊悔：这么简单的思路我咋想不出来呢？！然后下次再遇到别的题目，又重复一遍上述的思维怪圈，形成恶性循环。就在尝试证明这两个结论的时候，我又开始忍不住想看看答案，幸运的是找不到对这两个性质证明的答案，只能尝试自己解决。后来翻了《离散数学及其应用》，发现大O记法中等号的确切含义并不是相等，而是小于等于，进而领会到大O记法表示的其实是函数的集合，这才找到了证明的正确思路。然后又翻了《托马斯微积分》，再次确认自己对极限性质的应用没有问题，这才给出了完整的证明。但在找到思路之前，我又一次开始了对自己的自我攻击，俗称精神内耗：

这么简单的性质你怎么就证明不出来呢？你是不是脑子有问题啊？
你不是上了大半年的《数据结构》课吗？学那么多有什么用？
你以前也做不出来，现在还是做不出来，我看你真的是一点长进都没有
你就根本没看懂这本书，算了你还是看答案吧废物

越想越心烦，越想越没信心，首先就输给了心中的这些恶念，所以不管怎么学都始终有一种学不会，学不通的感觉。现在看来，这不是智商问题，是心理问题。

对这两个基本性质的证明是微不足道的，但我却从中发现了我自己身上长期以来存在的问题，即心态问题。从现在开始，我要斩断心中的这些执念，停止对自己的精神内耗，遇到问题多找方法，承认自己基础不扎实并多补基础，而不是遇到点困难一上来就开始自我PUA。人要在事上磨，方能见真功夫，毕竟

人生难得今生得，

佛法难闻今已闻。

此身不向今生渡，

更向何生渡此身？

对大O记号两个性质的证明

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读